tbquan08hanoi's blog

Prime nim?
By tbquan08hanoi, history, 2 hours ago, In English

Problem: A pile has n stones and 2 players: Player A go first. Each move, the player will take k stones from the pile, where k has to be prime. Whoever can't make a move first is lost. Problem has multiple test. Constraints: $$$1 <= t <= 100$$$: Number of tests $$$2 <= n <= 3 \cdot 10^6$$$: The number of stones in the pile Output: A if A wins, B if B wins.

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
113 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

its not a nim problem though (get it?)

→ Reply
»
99 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

Try applying sprague grundy theorem, You'll notice a pattern in it and after noticing it, you can come up to an O(1) solution.

You can study it from here How to calculate Grundy values?.

Pattern looks somewhat like this g(x) = x % 4

→ Reply
  • »
    »
    94 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Basically player B wins only when n % 4 == 0 otherwise A wins.

    → Reply
    • »
      »
      »
      83 minutes ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it
      • For n = 4: player A takes 3 stones, 1 stone left. I doubt B wins.
      • For n = 12: player A takes 11 stones.
      • For n = 20: player A takes 19 stones.

      So not always B wins when n % 4 == 0

      → Reply
    • »
      »
      »
      40 minutes ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      bs logic

      → Reply
»
97 minutes ago, # |
  Vote: I like it +4 Vote: I do not like it
If you have learned anything from the recent EDU round you would first

Some more possible variations of Nim to brighten your day

  • Divisor Nim
  • Non-divisor Nim (coprime and non-coprime numbers allowed)
  • Non-prime Nim, as opposed to presented variation
  • Non-coprime nim (opposite of last EDU round)
→ Reply