464. Optimal bribing
Time limit per test: 0.5
Memory limit: 262144
It is not easy to live and do business in Russia. For example, to get approval for gas utilities installation according to Russian law you need to get project documentation from city project bureau. But to get project documentation you will be required to get approval for gas utilities installation. Even to people who don't write computer programs and don't know buzz words like "endless recursion" it is clear that to get access to gas one needs to make a wonder. For example, to give bribe or kickback.
Suppose two businessmen compete for some business project which brings them profit V
. But only one businessman will be able to win the project — namely, the one who will get N
approvals from bureaucrats faster than another. Every businessman gets approvals in certain order — he cannot file next document for approval while previous document is not approved. To speed the process of getting approval up, businessmen may bribe bureaucrats. A businessman may visit (and bribe) only one bureaucrat a day. Specifically, if in particular day businessman i
gives to a bureaucrat bribe of b
units (non-negative real number which businessman defines itself, and b
may vary from day to day), probability that the bureaucrat will give him the approval at that day is 1-0.99(1-Fi
, where Fi
is businessman-specific fascination parameter (so, you see that without a bribe there is only 1 percent
chance to get an approval at a particular day). If bribing was unsuccessful, businessman may try again and again (and this doesn't change behavior of bureaucrat in any way), but he loses time (remember, businessman can give only one bribe a day) and money (since even in the case of unsuccessful bribe bureaucrat takes it). If a businessman gets an approval, he can file next document for approval on the next day (and at the same day bribe and get the document approved in the case of luck). Thus, even very lucky and fascinating businessman cannot have more than one document approved in one day. The first businessman who gets N
approvals wins the project and makes profit V
, another gets nothing (but loss from bribing). If businessmen get all necessary approvals at the same day, we consider that the winner is determined by coin tossing (that is, each of them has the same chance to win). Every businessman knows how many approvals the other one has at any moment.
Suppose that every businessman acts optimally to maximize expected difference between profit and costs (which is the total sum of bribes paid), knowing the strategy of another player. What is the probability to win the project for each of them?
Input file contains numbers N
from the problem statement. N
are integers, F1
are given with not more than two digits after decimal point (1 ≤ N
≤ 10, 0 < F1
< 1, 1 ≤ V
≤ 100). Numbers will be chosen so that businessmen will have unique equilibrium combination of optimal bribing strategies (so, required probabilities will be unique as well).
Write to the output file required probabilities with accuracy not less than 10-6
1 0.14 0.10 20