TopCoder problem "PowerGame" used in SRM 384 (Division II Level Three)



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 a String 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.
 

Definition

    
Class:PowerGame
Method:winner
Parameters:int, int
Returns:String
Method signature:String winner(int size0, int size1)
(be sure your method is public)
    
 

Constraints

-size0 and size1 will each be between 1 and 10000, inclusive.
 

Examples

0)
    
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.
1)
    
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.
2)
    
2
3
Returns: "Bob will win after 2 moves"
The only possible move for both players is removing one stick during each turn.
3)
    
7
13
Returns: "Bob will win after 4 moves"
4)
    
2136
1244
Returns: "Alan will win after 7 moves"

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7756

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10808&pm=7756

Writer:

rasto6sk

Testers:

PabloGilberto , Olexiy , lovro , ivan_metelsky

Problem categories:

Dynamic Programming