Gold Digging
시간 제한4초메모리 제한1024 MB
파손 확률과 채굴 비율이 주어진 금광들에서 기계 하나를 매일 최적으로 배정해 얻는 최대 기대 금의 양을 구한다.
문제
Mr. Goldust (1817-1890) was one of the first gold prospectors in the California Gold Rush. He literally struck gold there and became the owner of a few hundred gold pits. Mr. Goldust's great great great grandson Mr. Stardust currently owns the gold pits. Most of the gold has been dug up already, so Mr. Stardust wants to finish digging and get going to Las Vegas. A corporate giant offered to help him by supplying machines.
The machines are worth their weight in gold, so Mr. Stardust can only buy exactly one such machine. This machine was built using advanced science and thus does not work unless given appropriate working conditions.
Each day, Mr. Stardust will assign the machine to exactly one of the gold pits. If he assigns it to pit 'i', two things can happen:
- The machine will break down - with probability bi (0 < bi ≤ 1) . The machine cannot be used any more
- The machine will extract gold - with probability (1-bi) the machine will extract a proportion ri (0 ≤ ri ≤ 1) of the gold remaining in pit i
Theoretically the machine can last forever or break down very soon. So, Mr. Stardust's plan is to wait suitably long and then take off to Las Vegas. Of course, he will end up broke if the machine breaks down on day 1. He first needs to know how much gold he can expect to get using the machine optimally, that is, the best expected value of gold Mr. Stardust can achieve with an optimal strategy of allocating the machine to the pits.
입력
The input consists of a sequence of cases.
Each case starts with N (0 < N ≤ 100) on a line, representing the number of gold pits. Following this line are N lines, each one describing one pit. The ith line has three integers xi, yi and gi where bi = xi / 100, ri = yi / 100 and gi is the amount of gold in pit i. (1 ≤ xi ≤ 100, 0 ≤ yi ≤ 100 , 1 ≤ gi ≤ 100).
The last case will be followed by a -1. This case should not be processed.
There will be a maximum of 50 test cases.
출력
Output one case per line, the best expected value of gold that can be obtained, rounded to six decimal places.
힌트
In the first and second sample cases, keep assigning the machine to the only pit available. In the third sample case, clearly it is better to assign the machine to pit 1 on day 1 and if it survives, assign it to pit 2 from day 2 onwards.