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:
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.
Migrated from old NTUJ.
ICPC 2008, Amritapuri
| No. | Testdata Range | Score |
|---|