PotatoGame
SRM 472 · 2009-11-12 · by rng_58
SRM 472 · 2009-11-12 · by rng_58 · Math
Problem Statement
Problem Statement
Taro and Hanako like potatoes very much. Today they decided to play Potato Game.
Initially there is a box containing n potatoes. Taro and Hanako alternate turns, and Taro goes first. In each turn, the player must eat some potatoes from the box. The number of eaten potatoes must be a power of four, i.e., 1, 4, 16, 64 and so on. The first player who cannot eat a valid number of potatoes loses. Return the name of the winner assuming that they both play optimally.
Initially there is a box containing n potatoes. Taro and Hanako alternate turns, and Taro goes first. In each turn, the player must eat some potatoes from the box. The number of eaten potatoes must be a power of four, i.e., 1, 4, 16, 64 and so on. The first player who cannot eat a valid number of potatoes loses. Return the name of the winner assuming that they both play optimally.
Constraints
- n will be between 1 and 1,000,000,000 (10^9), inclusive.
Examples
0)
1 Returns: "Taro"
Taro will win if he eats 1 potato in the first turn.
1)
2 Returns: "Hanako"
Taro must eat exactly 1 potato in the first turn. In the second turn, Hanako will eat 1 potato and she will win.
2)
3 Returns: "Taro"
3)
4 Returns: "Taro"
4)
5 Returns: "Hanako"
Submissions are judged against all 111 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class PotatoGame with a public method string theWinner(int n) · 111 test cases · 2 s / 256 MB per case