| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 172 | 58 | 40 | 30.769% |
A speedrun is a playthrough of a game with the intention to complete it as quickly as possible. When speedrunning, you usually follow a pre-planned path through the game. Along this path, there may be some places where you have to pull off a difficult technique, or trick, which may cause a delay if you fail to pull it off successfully. Luckily you can reset the game at any time: if you have made a few mistakes, you can start a new run, losing your progress but instantaneously starting over with a clean slate. You can do this as often as you like.
The game you are currently speedrunning has a record of $r$ seconds, which you intend to beat. You have discovered a path through the game that, in the best case, takes $n < r$ seconds. There are some tricks along the way, though: you know exactly where along the run they occur, what the probability is that you will pull them off successfully, and how many seconds you have to spend to recover if they fail.
Given this data, you want to find the optimal strategy for when to reset the game to minimise the expected time to set a new record. Write a program to determine what this smallest possible expected time is.
The input consists of:
The tricks are given in sorted order by $t,ドル and no two tricks occur at the same time $t$ in the route.
You may assume that, without resetting, a single playthrough has a probability of at least 1ドル$ in 50ドル,000円$ to succeed at improving the record.
Output the expected time you will have to play the game to set a new record, assuming an optimal strategy is used. Your answer should have an absolute or relative error of at most 10ドル^{-6}$.
100 111 5 20 0.5 10 80 0.5 2 85 0.5 2 90 0.5 2 95 0.5 2
124
The record for this game is 111ドル$ seconds, and your route takes 100ドル$ seconds if everything goes right.
After playing for 20ドル$ seconds, there is a trick with a 50ドル\%$ success rate. If it succeeds, you keep playing. If it fails, you incur a 10ドル$ second time loss: now the run will take at least 110ドル$ seconds. It is still possible to set a record, but every other trick in the run has to be successful. It turns out to be faster on average to reset after failing the first trick.
Thus you repeat the first 20ドル$ seconds of the game until the trick is successful: with probability 1ドル/2,ドル it takes 1ドル$ attempt; with probability 1ドル/4,ドル it takes 2ドル$ attempts; and so on. On average, you spend 40ドル$ seconds on the first 20ドル$ seconds of the route.
Once you have successfully performed the first trick, you want to finish the run no matter the result of the other tricks: it takes 80ドル$ seconds, plus on average 1ドル$ second loss from each of the remaining 4ドル$ tricks. So the expected time until you set a record is 124ドル$ seconds.
2 4 1 1 0.5 5
3
10 20 3 5 0.3 8 6 0.8 3 8 0.9 3
18.9029850746
10 50 1 5 0.5 30
15
ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2020 G번