Revizia anterioară Revizia următoare
| 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
Date de iesire
Pentru fiecare din cele T teste, cate o linie care contine numarul de configuratii modulo 334214459.
Restrictii
1 <= n, m <= 128
Exemplu
chomp.in
1
2 2
chomp.out
6
Chomp
Jocul Chomp se joaca pe o tableta de ciocolata de n x m patratele, unde n >= 1 si m >= 1. Initial tableta este plina. Patratelele de ciocolata sunt indexate de la (1,1) pentru patratelul din stanga jos la (n,m) pentru patratelul din dreapta sus. Fiecare jucator face o cate o mutare pe rand. O mutare consta in alegerea unei coordonate (i,j) cu 1 <= i <= n si 1 <= j <= m la care exista inca ciocolata. Jucatorul care face mutarea (i, j) mananca toate patratelele de ciocolata care se gasesc la coordonate (y,x) cu y >= i si x >= j. Patratelul de la coordonate (1,1) este otravit. Jucatorul care este nevoit sa manance acest patratel pierde jocul.
Jocul Chomp este interesant din punct de vedere teoretic deoarece exista o demonstratie eleganta ca primul jucator are strategie sigura de castig. Demonstratia este bazata pe argumentului furtului de strategie. Pentru aceasta problema, nu este importanta demonstratia, deoarece se cere, dandu-se n si m, numarul de configuratii posibile in care poate ajunge jocul. Mai mult, fiindca comisia este de treaba, se cere sa se afiseze rezultatul modulo 334214459.
Date de intrare
Fişierul de intrare chomp.in, e prima linie, numarul T <= 100 de teste.
Pe fiecare din urmatoarele T linii, cate doua numere naturale n si m, reprezentand numarul de linii si numarul de coloane pentru tableta de ciocolata din testul respectiv.
Date de ieşire
În fişierul de ieşire chomp.out ...
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| chomp.in | chomp.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
