영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
You have just gotten a new battery-powered drone, but you lack batteries. In the store, there are N batteries available for the drone, each with an energy e_i, weight w_i, and cost c_i. The store has only one of each battery.
To have as much fun as possible with the drone, you obviously want it to fly as long as possible on a full charge. The time the drone can stay in the air is given by the expression t = (E_tot)/(W_tot) where E_tot is the total energy content of all the drone's batteries, and W_tot is the combined weight of the drone and the batteries.
Given a budget B and the weight of the drone itself W, determine the maximum time the drone can fly.
Input
The first line contains three integers N, B, and W (1 ≤ N × B ≤ 200,000 and 1 ≤ W ≤ 1000), the number of available batteries, your budget, and the weight of the drone.
The following N lines each contain three integers. Line number i contains e_i, w_i, and c_i (0 ≤ e_i ≤ 1000, 0 ≤ w_i ≤ 1000, 0 ≤ c_i ≤ B), the energy, weight, and cost of battery i.
Output
Print a decimal number: The longest time you can fly your drone if you choose the batteries optimally. The answer will be accepted if it has a relative or absolute error of at most 10^-5. That is, if your answer is a and the correct answer is b, your answer will be accepted if either |a-b| ≤ 10^-5 or (|a-b|)/(|b|) ≤ 10^-5.
Points
Your solution will be tested on several test case groups. To get the points for a group, it must pass all the test cases in the group.
| Group | Point value | Constraints |
|---|---|---|
| 1 | 10 | N ≤ 20 |
| 2 | 20 | w_i = 0 |
| 3 | 20 | c_1 = c_2 = … = c_N |
| 4 | 50 | No additional constraints. |
예제
예제 1
10 1000 20 40 40 40 1 1 1 70 30 60 100 20 700 80 50 200 30 1 200 100 100 1 20 1 500 30 20 100 70 50 100
3.17073170731707