Speedy Greedy is a professional speedrunner: they play a videogame repeatedly, with the aim of finishing it as quickly as possible.

The game that Speedy Greedy is currently tackling consists of N levels, numbered sequentially from 1 to N. Although these levels must be completed in order, each of them is independent of the others in terms of gameplay. That is, no event from one level can have a relevant effect on the next levels (unlike other games where items, spells, points, lives, etc. are carried over from one level to the next).

The current world record for the fastest completion time of the game is T seconds. Speedy Greedy is determined to beat this world record, with no concern for the margin. Whether the game is finished 1 second or 1000 seconds faster than the current record is irrelevant: what matters to Speedy Greedy is improving the world record.

Speedrunners often choose and adjust their actions dynamically during a run, depending on various factors such as the situation of their character in the game. It is also common to restart the game, as for example once T seconds have passed there is no more hope to beat the world record. Any run of the game can be restarted at any point. When a restart command is issued by the speedrunner, the game instantly restarts from the beginning. Thus, to beat the world record, Speedy Greedy must complete the N levels sequentially, in a single run that takes less than T seconds.

How can Speedy Greedy achieve that? Well, most sections of the game are completely safe and easy to play for a speedrunner of such skill. Those sections take fixed amounts of time and have no risk of failing. However, there is a very hard section in each of the N levels, where the result of playing that section is not completely under Speedy Greedy’s control, and also depends on the chosen strategy.

In each level, there are two possible strategies, and when reaching the hard section, Speedy Greedy can choose exactly one of them to attempt. Each strategy has its own probability of success, and the actual time that the level takes to complete depends on the chosen strategy and whether the attempt is successful or not.

For the purposes of this problem, we assume that Speedy Greedy can instantly detect whether the chosen strategy for a level succeeded or failed, right at the moment that the hard section of the level is reached. That is, reaching the hard section of a level, choosing a strategy, and knowing whether the attempted strategy succeeded or failed are all simultaneous events, occurring at exactly the same time.

Grinding the game by playing again and again and again becomes tiring and physically exhausting at such a high level of speedrunning competition. Speedy Greedy then decided to play the game so as to minimize the expected total play time until beating the world record. Your task is to compute this minimum.

Note that the total play time not only includes the time of the final successful run that takes less than T seconds (beating the world record), but also includes the time spent during all previous failed runs.

#6347 upload - done - how_to_reg - auto_awesome Special judge

Beating the Record timer 3s memory 1024MB

#6347
Special judge

Beating the Record 3s 1024MB