Statistics

Problem Statement for "AliceAndBobEasy"

Problem Statement

Alice and Bob are playing a game of NIM.

The rules of NIM are as follows: There are several piles of stones. The players take alternating turns. In each turn, the current player selects one non-empty pile of stones and removes some stones from the pile. (The player must remove at least one stone. They can remove as many stones as they want, possibly all of them, but just from a single pile.) The game ends when all stones have been removed. The player who removed the last stone wins the game. Equivalently, the first player who is unable to make a valid move loses the game.

More formally, a position in the game is an ordered sequence of pile sizes and a move consists of decrementing one of those values. Note that {1,2,3} and {3,2,1} are considered different positions, and thus the move from {3,2,3} to {1,2,3} and the move from {3,2,3} to {3,2,1} are two different moves.

Given a position, a move from that position is called a winning move if the player who plays that move can guarantee that from the resulting position they can win the game, even if their opponent plays optimally.

You are given the int N. Construct and return any position such that:

  • There are exactly N piles of stones.
  • Each pile has between 1 and 737,373,737 stones, inclusive.
  • All pile sizes are distinct.
  • The number of different winning moves from this position is as large as possible. (I.e., no other position that satisfies the previous items has more winning moves.)

Definition

Class:
AliceAndBobEasy
Method:
make
Parameters:
int
Returns:
int[]
Method signature:
int[] make(int N)
(be sure your method is public)

Constraints

  • N will be between 1 and 37, inclusive.

Examples

  1. 1

    Returns: {737 }

    In this position the active player has exactly one winning move: take all the stones.

  2. 2

    Returns: {737, 373 }

    In this position there is also exactly one winning move: take 364 stones from pile 0. There is no other valid position with more than one valid move.

  3. 3

    Returns: {3337, 3373, 3733 }

    Note that the pile sizes must be distinct. For example, { 373, 373, 373 } is not a valid answer.

  4. 4

    Returns: {1, 2, 5, 7 }

  5. 5

    Returns: {1, 5, 7, 9, 11 }

  6. 6

    Returns: {2, 3, 5, 7, 9, 11 }

  7. 7

    Returns: {3, 5, 7, 9, 11, 13, 15 }

  8. 8

    Returns: {1, 2, 5, 7, 9, 11, 13, 15 }

  9. 9

    Returns: {1, 5, 7, 9, 11, 13, 15, 17, 19 }

  10. 10

    Returns: {2, 3, 5, 7, 9, 11, 13, 15, 17, 19 }

  11. 11

    Returns: {3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23 }

  12. 12

    Returns: {1, 2, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23 }

  13. 13

    Returns: {1, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27 }

  14. 14

    Returns: {2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27 }

  15. 15

    Returns: {3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31 }

  16. 16

    Returns: {1, 2, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31 }

  17. 17

    Returns: {1, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35 }

  18. 18

    Returns: {2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35 }

  19. 19

    Returns: {3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39 }

  20. 20

    Returns: {1, 2, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39 }

  21. 21

    Returns: {1, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43 }

  22. 22

    Returns: {2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43 }

  23. 23

    Returns: {3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47 }

  24. 24

    Returns: {1, 2, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47 }

  25. 25

    Returns: {1, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51 }

  26. 26

    Returns: {2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51 }

  27. 27

    Returns: {3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55 }

  28. 28

    Returns: {1, 2, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55 }

  29. 29

    Returns: {1, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59 }

  30. 30

    Returns: {2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59 }

  31. 31

    Returns: {3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63 }

  32. 32

    Returns: {1, 2, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63 }

  33. 33

    Returns: {1, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67 }

  34. 34

    Returns: {2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67 }

  35. 35

    Returns: {3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71 }

  36. 36

    Returns: {1, 2, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71 }

  37. 37

    Returns: {1, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75 }

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: