BearEmptyCoin
SRM 695 · 2016-06-25 · by Errichto
Problem Statement
Bear Limak has a fair coin. (Whenever he tosses the coin, it will land on each side with probability 50%.) Initially, both sides of the coin are empty.
Limak is going to play a game. At the beginning of the game, Limak's score is 0. The game will consist of K turns. Each turn will look as follows:
- Limak tosses the coin.
- If the visible side of the coin is empty, Limak chooses an arbitrary (possibly negative or extremely big) integer and writes it on that side of his coin.
- Limak adds the integer written on the visible side of the coin to his score.
Limak will win the game if his final score (after all K turns) is exactly S. Limak is smart and always follows a strategy that maximizes the probability of winning the game.
You are given the
Constraints
- K will be between 1 and 60, inclusive.
- S will be between -1,000,000,000 and 1,000,000,000, inclusive.
1 17 Returns: 2
After tossing a coin, Limak should write 17 on the visible side. His final score will be 17. The probability of winning is 1. You should return 1 * 2K = 2.
2 -50 Returns: 4
An optimal strategy looks as follows: Toss the coin for the first time. Write -25 on the visible side. Add the number -25 to your score. Your score is now -25. Toss the coin for the second time. There are now two possibilities: either the visible side is empty, or it contains the -25 we wrote on the coin in the first round. If the visible side is empty, write -25 on that side as well. In either case, add -25 to your score. Your score is now -50. When following this strategy you are guaranteed to win the game. Again, you should return 1 * 2K.
2 -49 Returns: 2
In this case you cannot guarantee to win the game. The best strategy will give you a 50% probability of winning. The return value should be 0.5 * 2K = 2. One optimal strategy looks as follows: After the first coin toss, write 80,000,000,000 (i.e. 8 * 1010) on the visible side. Then, there are two possibilities for the second coin toss. If you see 80,000,000,000 again, your final score is 160,000,000,000 and you lose. If you see the other (still empty) side of the coin, you can write -80,000,000,049 and win the game beucase your final score is -49. Obviously, there are other optimal strategies as well: you can write any integer x after the first coin toss, and then hope to see the other side on the coin and write (-49-x) there.
4 42 Returns: 8
4 -123456789 Returns: 6
Submissions are judged against all 70 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BearEmptyCoin with a public method long long winProbability(int K, int S) · 70 test cases · 2 s / 256 MB per case