PowerGame
SRM 384 · 2007-12-19 · by rasto6sk
SRM 384 · 2007-12-19 · by rasto6sk · Dynamic Programming
Problem Statement
Problem Statement
Alan and Bob are playing a game with two piles of sticks. The two players alternate turns, and Alan gets the first turn. During each turn, the player must remove exactly n^2 sticks from each pile, where n is some positive integer. The value of n does not have to be the same for each pile.
For example, he can remove 1^2 = 1 stick from the first pile and 3^2 = 9 sticks from the second pile. The first player who cannot make a valid move is declared the loser.
The first pile initially contains size0 sticks and the second pile contains size1 sticks. Suppose both players play optimally. One of them has a winning strategy (no matter how his opponent plays he can always win) and he wants to win as fast as possible. The other player wants to lose as slowly as possible.
Return aString formatted as "<WINNER> will win after <NUMBER> moves" (quotes for clarity), where <WINNER> is the name of the winner and <NUMBER> is the total number of turns in the game. The total number of turns is the sum of all the successful turns taken by Alan and Bob.
The first pile initially contains size0 sticks and the second pile contains size1 sticks. Suppose both players play optimally. One of them has a winning strategy (no matter how his opponent plays he can always win) and he wants to win as fast as possible. The other player wants to lose as slowly as possible.
Return a
Constraints
- size0 and size1 will each be between 1 and 10000, inclusive.
Examples
0)
10000 10000 Returns: "Alan will win after 1 moves"
1)
4 9 Returns: "Alan will win after 1 moves"
A player can take 1, 4, 9, 16, 25, ... sticks. Alan can make all the piles empty in his first move, leaving Bob with no valid moves. He will win the game after 1 turn.
2)
4 3 Returns: "Alan will win after 1 moves"
Alan can remove all the sticks from the first pile in his first turn, leaving Bob with no valid moves.
3)
2 3 Returns: "Bob will win after 2 moves"
The only possible move for both players is removing one stick during each turn.
4)
7 13 Returns: "Bob will win after 4 moves"
Submissions are judged against all 43 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class PowerGame with a public method string winner(int size0, int size1) · 43 test cases · 2 s / 256 MB per case