Orange Boy Can You Solve It Out? Ep.17

思考题 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 p_i to pass. If he fails, he will have to retry from the beginning of the stage again.
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 b_i. But ZJS has only B bombs. That's why he decided to use them wisely.
Note that, after retrying a stage with a bomb, the probability of passing that stage is still b_i, and ZJS never put two bombs in a single stage.
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.


Subtask 1(30%):N=6,B=3
Subtask 2(30%):N,B<=20
Subtask 3(10%):N,B<=100
Subtask 4(10%):N,B<=1000
Subtask 5(10%):N,B<=1e5
Subtask 6(5%):N<=1e5,B=0
Subtask 7(5%):N<=1e5,B=1
For all subtask, 0<=B<=N<=1e5 holds.

来源:Hell Hole Studios Blog

< <上一篇