Statistics

Problem Statement for "PowerGame"

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

  1. 10000

    10000

    Returns: "Alan will win after 1 moves"

  2. 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.

  3. 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.

  4. 2

    3

    Returns: "Bob will win after 2 moves"

    The only possible move for both players is removing one stick during each turn.

  5. 7

    13

    Returns: "Bob will win after 4 moves"

  6. 2136

    1244

    Returns: "Alan will win after 7 moves"

  7. 3

    5

    Returns: "Bob will win after 2 moves"

  8. 1

    1

    Returns: "Alan will win after 1 moves"

  9. 1

    10000

    Returns: "Alan will win after 1 moves"

  10. 28

    17

    Returns: "Alan will win after 7 moves"

  11. 884

    5521

    Returns: "Alan will win after 15 moves"

  12. 9113

    2842

    Returns: "Alan will win after 23 moves"

  13. 6673

    8111

    Returns: "Alan will win after 25 moves"

  14. 24

    9019

    Returns: "Alan will win after 5 moves"

  15. 502

    213

    Returns: "Alan will win after 9 moves"

  16. 9999

    9999

    Returns: "Alan will win after 31 moves"

  17. 9112

    9112

    Returns: "Alan will win after 21 moves"

  18. 7172

    42

    Returns: "Alan will win after 9 moves"

  19. 8806

    9753

    Returns: "Alan will win after 31 moves"

  20. 2224

    5813

    Returns: "Alan will win after 5 moves"

  21. 8444

    8444

    Returns: "Alan will win after 35 moves"

  22. 9013

    9017

    Returns: "Alan will win after 15 moves"

  23. 46

    47

    Returns: "Alan will win after 5 moves"

  24. 883

    7721

    Returns: "Alan will win after 17 moves"

  25. 2

    2

    Returns: "Bob will win after 2 moves"

  26. 3

    3

    Returns: "Alan will win after 3 moves"

  27. 4

    4

    Returns: "Alan will win after 1 moves"

  28. 5

    5

    Returns: "Bob will win after 2 moves"

  29. 99

    99

    Returns: "Alan will win after 13 moves"

  30. 4234

    3852

    Returns: "Alan will win after 17 moves"

  31. 515

    61

    Returns: "Alan will win after 7 moves"

  32. 8

    8887

    Returns: "Alan will win after 5 moves"

  33. 6642

    6642

    Returns: "Bob will win after 40 moves"

  34. 4009

    4009

    Returns: "Alan will win after 29 moves"

  35. 4567

    8671

    Returns: "Alan will win after 9 moves"

  36. 8999

    9999

    Returns: "Alan will win after 19 moves"

  37. 4563

    2314

    Returns: "Alan will win after 5 moves"

  38. 3454

    4456

    Returns: "Alan will win after 31 moves"

  39. 9563

    8914

    Returns: "Alan will win after 25 moves"

  40. 9000

    8999

    Returns: "Alan will win after 19 moves"

  41. 9876

    1234

    Returns: "Alan will win after 15 moves"

  42. 9456

    8754

    Returns: "Alan will win after 21 moves"

  43. 10

    10

    Returns: "Bob will win after 4 moves"

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: