思考题 for Hakurei Reimu
Legacy of Lunatic Kingdom
ZJS loves playing Touhou. In the famous STG game Touhou:Legacy of Lunatic Kingdom the game rules are defined as follows:
The game consists of N "stages". Player start from Stage 1 and ends at Stage N. In i-th stage, our little ZJS has a probability
But, ZJS has some BOMBs. He can use BOMB in some stages.The probability of the stage i to pass after using a bomb is
Note that, after retrying a stage with a bomb, the probability of passing that stage is still
Assume that beating each stage once needs 1 unit of time. For each bomb placement, you need to calculate the expected time to pass all stages. Then you need to print the minimum one among all these data. If the minimum one is INF, print -1 instead.
YP is calling him so he asked the Orange Boy to help.
For all subtask, 0<=B<=N<=1e5 holds.