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

版权声明：

作者：XGN

链接：__https://blog.hellholestudios.top/archives/224__

来源：Hell Hole Studios Blog

文章版权归作者所有，未经允许请勿转载。

## 共有 0 条评论