| Fişierul intrare/ieşire: | chomp.in, chomp.out | Sursă | ACM ICPC Faza Nationala 2015 |
| Autor | Stefan Ciobaca | Adăugată de |  ONIS2015 •ONIS2015 |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | chomp.out |
|---|---|
| 1 2 2 | 6 |
