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.

Constriants

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.
th15

版权声明:
作者:XGN
链接:https://blog.hellholestudios.top/archives/224
来源:Hell Hole Studios Blog
文章版权归作者所有,未经允许请勿转载。

THE END
分享
二维码
< <上一篇
下一篇>>