DMOPC '15 Contest 7 P3 - Harbourmaster - Olympiads Online Judge

DMOPC '15 Contest 7 P3 - Harbourmaster

Points: 7 (partial)

Time limit: 1.0s

Memory limit: 64M

Author:

Problem type

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$ $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\%$ $100 %$ . For example, if both the Anti-seasickness and Pathfinding requirements are met while the requirement for Coding is $100$ $100$ but the crew only provides $50$ $50$ , the voyage's chance of success will be $50\%$ $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$ $C, S, P$ representing the voyage's Coding, Anti-seasickness, and Pathfinding requirements respectively $(0 \le C, S, P \le 10^6)$ $(0 \leq C, S, P \leq 10^{6})$ .
The second line of input will contain $N$ $N$ $(1 \le N \le 25)$ $(1 \leq N \leq 25)$ .
For the next $N$ $N$ lines, line $i$ $i$ will represent the attributes of the $i$ $i$ -th crew member $C_i, S_i, P_i$ $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)$ $(0 \leq C_{i}, S_{i}, P_{i} \leq 10^{6})$ .

Output Specification

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

Sample Input

Copy

Sample Output

Copy

2.0

Explanation

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

Comments

5

kobortor commented on April 12, 2016, 9:16 p.m.

.

1

cheesecake commented on April 12, 2016, 9:27 p.m. ← edit 2 →

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\%$ $100 %$ .