Orange Boy Can You Solve It Out? Ep. 39
Have you ever played Super Mario Maker (2)? There's an interesting mode called Endless Challenge. Let's look at a simplified version:
The game contains N levels. The player plays from level 1 to level N in order. In Level i, there are Ai 1-UP mushrooms and Bi coins. When player collects one 1-up mushrooms, he will gain one extra life. When player collects 100 coins, it will be converted into a 1-up mushroom at the exact moment. One cannot gain more than 3 lifes in a level. Moreover, the player have 0 lifes at first.
After beating these N lifes, each life will be converted into 1 point, each coin will be converted into 0.01 point. Assume the player plays well enough and never lose life. What's the maximum point you will get?
In level one, we collect 1 1-up mushroom and 10 coins, now Life=1 Coin=10
In level two, we collect 2 1-up mushrooms and 100 coins. The first 90 coins altogether with the coins we collected in the first level convert to 1 life, now Life=4 Coin=10
In level three, we collect 3 1-up mushrooms and 120 coins. The first 90 coins altogether with the coins we have convert to 1 life. But we've already gained 3 lifes in this level by collecting 1-up mushrooms, so these lives don't count. Now life=7 Coin=30
We collect 99 coins in the first level and 100 in the second.
If you collect 100 coins in the first level, the answer is 1.00 which is worse.
Subtask 1(30%): N<=1000
Subtask 2(30%): N<=10000
Subtask 3(30%): N<=100000
Subtask 4(10%): N<=1000000
DP works to subtask 2. I wonder if we can cheese by greedy
来源：Hell Hole Studios Blog