Problem I. Item Enhancement II ≡
| Author: | A. Verkholat | Time limit: | 1 sec | |
| Input file: | Standard input | Memory limit: | 256 Mb | |
| Output file: | Standard output |
Statement
Petya likes to play MMORPG and wants to beat everyone in PvP.
He just bought and enhanced an awesome weapon, but he didn't have enough money for armor.
Fortunately, the server he plays on supports the transfer of enhancement levels, and Petya knows how to make money from it.
He buys cheap items, and if they get a high enhancement level, he can sell them for a high price
To determine if this is a profitable strategy, certain calculations need to be made.
However, Petya is not the best programmer/mathematician, so he asks for your help.
The starting enhancement level of an item is 0.
The maximum possible level is 12.
To increase the enhancement level by 1 with a certain probability, 1 Immortal Stone is required.
In case of failure, the enhancement level of the item resets to zero (exceptions are specified below).
Additionally, along with the Immortal Stone, one special stone can be used.
The server offers the following special stones:
Sky Stone - significantly increases the chances of success.
Underground Stone - slightly increases the chances of success, in case of failure it decreases the enhancement level by 1.
Stone of Creation - has low chances of success, but in case of failure it does not reduce the enhancement level.
I-th level Dragon Orb - guarantees successful enhancement up to level I and lower, no effect for other levels.
Petya knows the prices of all the required resources and the chances of successful enhancement.
You should calculate the minimum average cost for each level so that Petya can assess which level is most profitable to trade.
Input format
The first line contains an integer T - the number of input data sets.
Next follows the description of each set.
The first line contains four integers: A, B, C, D:
A: price of an Immortal Stone.
B: price of a Sky Stone.
C: price of an Underground Stone.
D: price of a Stone of Creation.
The next 12 lines contain the following numbers: Wi, Xi, Yi, Zi, Ei:
Wi: chance of success for level i with Immortal Stone.
Xi: chance of success for level i with Immortal Stone + Sky Stone.
Yi: chance of success for level i with Immortal Stone + Underground Stone.
Zi: chance of success for level i with Immortal Stone + Stone of Creation.
Ei: an integer, the price of i-th level Dragon Orb.
Output format
For each input data set, output 12 lines.
In the i-th line a single integer (rounded down) - the minimum average cost of i-th level enhancement.
Constraints
1 ≤ T ≤ 500
1 ≤ A, B, C, D, Ei ≤ 109
0.05 ≤ Wi, Xi, Yi ≤ 0.95
0.0001 ≤ Zi ≤ 0.95
Zi ≤ Wi ≤ Yi ≤ Xi
Sample tests
| No. | Standard input | Standard output |
|---|---|---|
| 1 | |
|