The Game of Nim

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 1.4s
Memory limit: 128M

Author:
Problem types

There are N (1 \le N \le 1000) piles of stones. Each pile has at least 1 and at most 1000 stones in it. You are bored, and decide to play a game with the stones. The rules of this game are as follows:

  • during a players turn, if there are no stones left, that player loses
  • otherwise, a player may take any positive number of stones from any one pile (of course, you can't take stones from an empty pile, but if the pile has at least one stone, you can take the whole pile)
  • if it's the very first turn of the game, the first player may choose to pass (that is, take 0 stones from any pile)

Write a program to play this game against a computer AI. You always go first.

To take X stones from pile P, output P X where 1 \le P \le N and 1 \le X \le \text{number of stones in pile }P.

The AI will produce output in a similar fashion.

If you win, the AI will output 0 0. Your program should terminate if you win or lose.

Input Specification

The first line of input will have N.

The (i+1)-th line will have the number of stones in pile i.

Output Specification

Please flush your output properly.

Sample Interaction

>>> denotes your output; don't actually print this out.

3
1
2
3
>>> 1 1
2 1
>>> 3 1
3 2
>>> 2 1
0 0

Explanation for Sample Interaction

Since the AI is unable to take a stone, you win.


Comments


  • 4
    bruce  commented on March 4, 2015, 2:52 a.m.

    AI should win after the first step of the player.