Az I. 361. feladat (2014. december)

I. 361. A korong lövés nevű játékot egy ember játssza egy \(\displaystyle N\) csúcsú egyszerű gráfon (\(\displaystyle 1\le N\le 20\)). A játék a következőképp néz ki: a gráf minden csúcsán van néhány korong. Egy lépésben a játékos fog egy tetszőleges csúcsot, és ha azon legalább annyi korong van, mint a csúcs szomszédainak száma (azon csúcsok, melyekkel éllel van összekötve), akkor minden szomszédnak ad egy-egy korongot. Akkor nyer a játékos, ha már nem tud ilyen lépést végrehajtani. Adjuk meg, hogy tud-e nyerni egy bizonyos alapállásból a játékos.

Segítség: ha tud nyerni a játékos, akkor bármilyen sorrendben választhatja a csúcsokat, amikkel lép, előbb-utóbb véget ér a játék. Ezt használjuk fel. Továbbá könnyítésképpen, ha ezzel a módszerrel 1000 lépés alatt nem fejeződik be a játék, akkor írjuk ki azt, hogy NEM tud nyerni.

A program a standard bemenet első sorából olvassa be az \(\displaystyle N\) és \(\displaystyle M\) (élek száma) számokat. A következő \(\displaystyle N\) sorban a gráf egyes csúcsain lévő korongok számát, majd a következő \(\displaystyle M\) sorból a gráf leírását: minden sorban egy \(\displaystyle a\) és egy \(\displaystyle b\) szám szerepel, ami azt jelenti, hogy az \(\displaystyle a\) csúcs szomszédja \(\displaystyle b\), és a \(\displaystyle b\) csúcs szomszédja \(\displaystyle a\). A program írja ki a standard output első sorába a NEM szót, amennyiben a segítségben leírt módszerrel 1000 lépés alatt nem fejeződik be a játék. Ha befejeződik, akkor az IGEN szót, és az alatta lévő \(\displaystyle N\) sorban pedig a végállapotban az egyes csúcsokon lévő számokat a bemenet sorrendjében.

Beküldendő egy tömörített i361.zip állományban a program forráskódja (i361.pas, i361.cpp, ...) az .exe és más, a fordító által generált állományok nélkül, valamint a program rövid dokumentációja (i361.txt, i361.pdf, ...), amely a fentieken túl megadja, hogy a forrás mely fejlesztői környezetben fordítható.

(10 pont)

A beküldési határidő 2015. január 12-én LEJÁRT.

Statisztika:

15 dolgozat érkezett.
10 pontot kapott:	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 pontot kapott:	Lencsés Ádám, Rittgasszer Ákos.

A KöMaL 2014. decemberi informatika feladatai