EOJ Test Round #7

C. Nim

单点时限: 3.0 sec

内存限制: 1024 MB

Nim is a famous take-away game, played as follows. There are $n$ piles of chips containing $x_1, x_2, \ldots, x_n$ chips respectively. (Piles of sizes $5$, $7$, and $9$ make a good game.) Two players take turns moving. Each move consists of selecting one of the piles and removing chips from it. You may not remove chips from more than one pile in one turn, but from the pile you selected you may remove as many chips as desired, from one chip to the whole pile. The winner is the player who removes the last chip.

My comment: This statement is from a course material in CMU. As you may know, this is a famous game with a lot of research done on optimal strategies. And your task, is to beat the computer, or claim that you will lose no matter what effort you have done.


The computer will first tell you about the piles:

  • First line is an integer $n$ ($1 \le n \le 100$);
  • Second line contains $n$ space-separated integers $x_1,x_2,\ldots,x_n$ ($1 \le x_i < 2^{10}$).

Then the game starts. You are the first player.

Each time, you should output two integers $k$ and $v$, meaning that you want to take $v$ chips from the $k$-th pile. $k$ should be between $1$ and $n$ and $v$ should be an positive integer not exceeding the current chip number in the $k$-th pile.

Computer responds in the same way.

If you claim that you are doomed to lose and don’t want to play any more, you should output -1 -1 so that computer will also quit the game. Your program should also terminate when all the chips have been removed. Computer will never output -1 -1 – it will fight till the end.

Judgement is as follows:

  • If you lose and the game theory proves that you must lose, you pass the test.
  • If you lose and the game theory claims that you should win, you fail the test.
  • Otherwise, you win; so you pass the test.


5 7 9

2 7
1 5

3 9


To flush you can use (just after printing an integer and end-of-line):

  • fflush(stdout) in C++;
  • System.out.flush() in Java;
  • stdout.flush() in Python;
  • flush(output) in Pascal;