Fişierul intrare/ieşire:chomp.in, chomp.outSursăACM ICPC Faza Nationala 2015
AutorStefan CiobacaAdăugată deONIS2015ONIS2015 ONIS2015
Timp execuţie pe test0.1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Chomp

Jocul Chomp se joacă pe o tabletă de ciocolată de n x m pătrăţele, unde n >= 1 şi m >= 1. Iniţial tableta este plină. Pătrăţelele de ciocolată sunt indexate de la (1,1) pentru pătrăţelul din stânga jos la (n,m) pentru pătrăţelul din dreapta sus. Jucătorii fac câte o mutare pe rând. O mutare constă în alegerea unei coordonate (i,j) cu 1 <= i <= n şi 1 <= j <= m la care există încă ciocolata. Jucătorul care face mutarea (i, j) mănâncă toate pătrăţelele de ciocolată care se găsesc la coordonate (y,x) cu y >= i şi x >= j. Pătrăţelul de la coordonatele (1,1) este otrăvit. Jucătorul care este nevoit să mănânce acest pătrăţel pierde jocul.

Jocul Chomp este interesant din punct de vedere teoretic deoarece există o demonstraţie elegantă că primul jucător are strategie sigură de câştig. Demonstraţia este bazată pe argumentului furtului de strategie. Pentru această problemă, nu este importantă demonstraţia, deoarece se cere, dându-se n şi m, numărul de configuraţii posibile în care poate ajunge jocul fără a ţine cont de modul în care s-a ajuns la configuraţia respectivă sau de jucătorul aflat la mutare. Mai mult, fiindcă comisia este de treaba, se cere să se afişeze rezultatul modulo 334214459.

Date de intrare

Fişierul de intrare chomp.in conţine, pe prima linie, numărul T <= 100 de teste. Pe fiecare din următoarele T linii, câte două numere naturale n şi m, reprezentând numărul de linii şi numărul de coloane pentru tableta de ciocolată din testul respectiv.

Date de ieşire

În fişierul de ieşire chomp.out, pentru fiecare din cele T teste, câte o linie care conţine numărul de configuraţii modulo 334214459.

Restricţii

  • 1 <= n, m <= 128

Exemplu

chomp.inchomp.out
1
2 2
6
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?