Problem I. 361. (December 2014)

I. 361. The ``disc shooting game'' is a single-person game played on a simple graph on \(\displaystyle N\) vertices (\(\displaystyle 1\le N\le 20\)) in the following way. Initially some discs are placed on every vertex. In a given step the player selects an arbitrary vertex, and if the number of discs on that vertex is greater than or equal to the number of neighbors of the vertex, then the player distributes one disc from the vertex to each neighbor (two vertices are neighbors if they are directly connected by an edge). The player wins if no such distribution is possible. Your task is to determine, for a given initial state, whether or not the player can win. You can use and assume the following hints: \(\displaystyle (i)\) if it is possible for the player to win, then the vertices can be selected in an arbitrary order, and - sooner or later - the game will end; \(\displaystyle (ii)\) if the game is still played after 1000 steps, then you should display a CANNOT WIN message.

Your program should read \(\displaystyle (i)\) the values of \(\displaystyle N\) and \(\displaystyle M\) (the number of vertices) from the first line of the standard input; \(\displaystyle (ii)\) the number of discs initially placed on the vertices from the following \(\displaystyle N\) lines; \(\displaystyle (iii)\) finally, the graph description from the last \(\displaystyle M\) lines: each such line contains two numbers, \(\displaystyle a\) and \(\displaystyle b\), meaning that vertex \(\displaystyle a\) and vertex \(\displaystyle b\) are neighbors. Your program should write the message CANNOT WIN to the first line of the standard input if the game does not end in 1000 steps as given in the above hint. If the game ends, then a CAN WIN message should appear, together with the number of discs on each vertex in the final state in the following \(\displaystyle N\) lines (by using the same vertex ordering as in the input).

In the table two sample inputs (``Példa bemenet'') and their corresponding output (``Kimenet'') are presented, with IGEN meaning CAN WIN, and NEM meaning CANNOT WIN.

The source code (i361.pas, i361.cpp, ...) without the .exe or any other auxiliary files generated by the compiler but with a short documentation (i361.txt, i361.pdf, ...), also describing which developer environment to use for compiling the source, should be submitted in a compressed file i361.zip.

(10 pont)

Deadline expired on January 12, 2015.

Statistics:

15 students sent a solution.
10 points:	Dombai Tamás, Fehér Balázs, Fényes Balázs, Gercsó Márk, Hamrik Szabin, Kazal Soma, Kiss 107 Ádám, Kovács 246 Benedek, Mócsy Miklós, Németh 729 Gábor, Olexó Gergely, Radnai Bálint, Szemerédi Levente.
9 points:	Lencsés Ádám, Rittgasszer Ákos.

Problems in Information Technology of KöMaL, December 2014