CSES - Datatähti Open 2018 - Heap Game
  • Time limit: 1.00 s
  • Memory limit: 512 MB
Justiina and Kotivalo are playing a game, whose initial setting consists of $n$ heaps of coins and a chosen parameter $a$. Justiina begins the game, and the players move alternately. The winner of the game is the player who makes the last move.

At each move the player chooses one of the heaps and removes some number of coins from it. After this, they keep $1 \ldots a$ coins and distribute the remaining coins back to the game. Each coin can be added to any existing heap or as the first coin in a new heap.

Can Justiina win the game if she plays optimally? And what is a possible winning opening move?


The first input line contains two integers $n$ and $a$: the number of heaps and the parameter $a$.

The next line contains $n$ integers $p_1,p_2,\ldots,p_n$: the number of coins in each heap.


First print "YES" if Justiina can win the game and "NO" otherwise.

If Justiina can win, print also an example how she can make her opening move. First print two lines, the first of the form "TAKE $x$ $y$" and the second of the form "KEEP $z$". This means that Justiina takes $y$ coins from a heap that has $x$ coins, and keeps $z$ coins. After this, print some number of lines of the form "ADD $x$ $y$". This means that Justiina adds $y$ coins to a heap that already contains $x$ coins. It is allowed that $x=0$ which creates a new heap. Finally, print a line "END" which ends the description of the move.

Example 1

3 2
1 3 2

TAKE 3 3
ADD 1 1

Explanation: Justiina removes all coins from the heap that contains three coins. Then she keeps two coins and adds one coin to the heap that already contains one coin. After the move, there are two heaps in the game and both of them contain two coins.

Example 2

3 1
1 3 2


Subtask 1 (17 points)
  • $1 \le n \le 5$
  • $1 \le a \le 2$
  • $1 \le \sum p_i \le 5$
Subtask 2 (22 points)
  • $1 \le n \le 20$
  • $1 \le a \le 5$
  • $1 \le \sum p_i \le 20$
Subtask 3 (61 points)
  • $1 \le n \le 500$
  • $1 \le a \le 500$
  • $1 \le p_i \le 500$