DMOPC '15 Contest 7 P3 - Harbourmaster

View as PDF

Submit solution


Points: 7 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

FatalEagle is playing a game. In this game, players send out ships to complete voyages for profit. Each voyage has numerical requirements in at least one of the Coding, Anti-seasickness, and Pathfinding attributes (its programmer crew must remain both mentally healthy by programming, and physically healthy by eating decent food, all while not getting lost). The closer a player's ship comes to fulfilling these requirements, the greater its chance of success. A ship can hold five crew members, and each member contributes some constant to their ship's attributes. FatalEagle has N such crew members, which he may assign to any ship.

A voyage's chance of success is defined as the minimum ratio between a voyage attribute and the sum of all crew members in that attribute, and maxes out at 100\%. For example, if both the Anti-seasickness and Pathfinding requirements are met while the requirement for Coding is 100 but the crew only provides 50, the voyage's chance of success will be 50\%.

Since FatalEagle has to manage many ships at once, determining his maximum chance of success would go a long way towards increasing his status as a harbourmaster. Can you help him?

Input Specification

The first line of input will contain three integers C, S, P representing the voyage's Coding, Anti-seasickness, and Pathfinding requirements respectively (0 \le C, S, P \le 10^6).
The second line of input will contain N (1 \le N \le 25).
For the next N lines, line i will represent the attributes of the i-th crew member C_i, S_i, P_i in the same order as given for the voyage (0 \le C_i, S_i, P_i \le 10^6).

Output Specification

FatalEagle's maximum chance of success if he assigns his crew optimally, rounded to one decimal place.

Sample Input

10 10 100
2
0 5 0
9 0 2

Sample Output

2.0

Explanation

The crew got lost, because while the voyage had 90\% Coding and 50\% Anti-seasickness, their Pathfinding total was 2.0\%.


Comments


  • 4
    kobortor  commented on April 12, 2016, 5:16 p.m.

    .


    • 1
      cheesecake  commented on April 12, 2016, 5:27 p.m. edited

      A voyage's chance of success is defined as the minimum ratio between a voyage attribute and the sum of all crew members in that attribute, and maxes out at 100%.