CP2012 – Chomp

by Mithrandir

Prima problemă din cadrul concursului de programare pe 2012 este inspirată dintr-un joc matematic simplu.

Este vorba de Chomp. Ne vom opri la cazul 2D pentru problema actuală și-l vom modela exact ca în articol pe baza unei ciocolate (poftă bună :P) Ideea e simplă: se dă o ciocolată și cine mănâncă ultimul pătrățel din ea pierde jocul. În momentul în care selectezi un pătrățel pentru a-l mânca trebuie să mănânci toate pătrățelele la dreapta și în jos.

Matematic, problema este echivalentă cu a porni de la un șir de numere [n, n, n, n, ... n] și a reduce pe rând numerele din șir păstrând o restricție de monotonie: la orice moment de timp șirul este descrescător (strict necrescător). Cel care este forțat să ajungă în poziția [0, 0, .... 0] pierde.

Teoria jocurilor clasifică toate pozițiile dintr-un joc cu informație totală în funcție de cine câștigă ca fiind safe (jucătorul care urmează să joace pierde) sau unsafe. Alternativ, definițiile sunt de P (jucătorul care a ajuns în poziție câștigă) sau N (jucătorul care pleacă din poziție câștigă). Dintr-o poziție P se poate ajunge doar în poziții N în timp ce orice poziție N garantează existența unei mutări ce va duce într-o poziție P. Evident, [0, 0, ... 0] este o poziție N la fel ca și [n, n, n, n, ... n].

Cerința problemei e simplă: fiind dată o listă de poziții în diverse jocuri de Chomp să se specifice dacă acestea sunt poziții P sau N.

Fiecare poziție este specificată prin șirul valorilor și este dată pe un singur rând la standard input. De exemplu

2 2 1
3 1 1
2 1
2 2

reprezintă o intrare validă pentru programul vostru. Outputul trebuie să fie litera P sau N, câte una pe linie, corespunzătoare fiecărei poziții primite la intrare.

P
P
P
N

Există 100 de teste, fiecare o singură poziție.

Ponderea problemei în clasamentul final este 1.

Spor.

PS: Ar putea fi util și articolul de aici.

PPS: Ca istorie, problema asta m-a pasionat din liceu, din când în când mă mai jucam cu ea. Unii matematicieni oferă premiu pentru instanțele mai grele ale ei, dacă vă pasionează/atrage puteți să încercați.