Statistics

Problem Statement for "ThueMorseGame"

Problem Statement

Alice and Bob play a game with a pile of stones. Initially, there are n stones in the pile. The players take alternating turns, Alice goes first. Each turn of the game looks as follows:
  1. The current player choses a number X between 1 and m, inclusive. X cannot exceed the current number of stones in the pile.
  2. The current player removes X stones from the pile.
  3. If the pile is now empty, the current player wins the game.
  4. The current player counts the remaining stones in the pile, and writes that count in binary. If that number contains an odd number of ones, the current player loses the game.
For example, the number 19 written in binary is 10011. This number has three ones in binary, and three is an odd number. Hence, whenever a player produces a pile with exactly 19 stones, they lose the game immediately. You are given the ints n and m. Assume that both Alice and Bob play the game optimally. Return "Alice" if Alice wins, or "Bob" if Bob wins. In other words, return "Alice" if and only if the first player has a winning strategy for the given n and m.

Definition

Class:
ThueMorseGame
Method:
get
Parameters:
int, int
Returns:
String
Method signature:
String get(int n, int m)
(be sure your method is public)

Constraints

  • n will be between 1 and 500,000,000, inclusive.
  • m will be between 1 and 50, inclusive.
  • n will have an even number of ones in binary.

Examples

  1. 100000000

    47

    Returns: "Alice"

  2. 3

    1

    Returns: "Bob"

  3. 99999957

    50

    Returns: "Alice"

  4. 99999988

    49

    Returns: "Bob"

  5. 99999974

    48

    Returns: "Bob"

  6. 167959139

    2

    Returns: "Bob"

  7. 141009859

    46

    Returns: "Alice"

  8. 423264237

    41

    Returns: "Alice"

  9. 202209411

    31

    Returns: "Alice"

  10. 85325539

    21

    Returns: "Alice"

  11. 58376259

    20

    Returns: "Alice"

  12. 72235422

    48

    Returns: "Alice"

  13. 43705451

    13

    Returns: "Bob"

  14. 496511007

    50

    Returns: "Alice"

  15. 495527937

    50

    Returns: "Alice"

  16. 499540828

    50

    Returns: "Alice"

  17. 499953832

    50

    Returns: "Alice"

  18. 499996436

    50

    Returns: "Alice"

  19. 499999999

    2

    Returns: "Bob"

  20. 499999999

    3

    Returns: "Bob"

  21. 499999999

    4

    Returns: "Bob"

  22. 499999999

    5

    Returns: "Bob"

  23. 499999979

    26

    Returns: "Bob"

  24. 499999987

    39

    Returns: "Bob"

  25. 499999963

    41

    Returns: "Bob"

  26. 499999999

    44

    Returns: "Bob"

  27. 499999975

    49

    Returns: "Bob"

  28. 499999951

    50

    Returns: "Bob"

  29. 3

    1

    Returns: "Bob"

  30. 499999999

    1

    Returns: "Bob"

  31. 18

    39

    Returns: "Alice"

  32. 75

    26

    Returns: "Alice"

  33. 359

    46

    Returns: "Alice"

  34. 237

    41

    Returns: "Alice"

  35. 411

    31

    Returns: "Alice"

  36. 39

    21

    Returns: "Alice"

  37. 270

    48

    Returns: "Alice"

  38. 449

    25

    Returns: "Alice"

  39. 311

    24

    Returns: "Alice"

  40. 3

    3

    Returns: "Alice"

    Here Alice can take three stones from the heap and win.

  41. 3

    2

    Returns: "Bob"

    If Alice can take one or two stones. Either case, remaining number of stones will contain an odd number of ones in binary.

  42. 387

    22

    Returns: "Alice"

  43. 499999999

    50

    Returns: "Alice"

  44. 499999975

    49

    Returns: "Bob"

  45. 400000000

    47

    Returns: "Alice"

  46. 5

    1

    Returns: "Bob"

  47. 402653184

    3

    Returns: "Alice"

  48. 6

    2

    Returns: "Bob"

  49. 57

    50

    Returns: "Alice"

  50. 499999975

    50

    Returns: "Alice"

  51. 6

    1

    Returns: "Alice"

  52. 9

    6

    Returns: "Bob"

  53. 450000000

    1

    Returns: "Alice"

  54. 6

    3

    Returns: "Alice"

  55. 51

    50

    Returns: "Bob"

  56. 54

    10

    Returns: "Alice"

  57. 20

    1

    Returns: "Bob"

  58. 9010

    50

    Returns: "Bob"

  59. 30

    20

    Returns: "Alice"

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: