bq. Doi participanţi mănâncă alternant din nişte tablete de ciocolată după următoarele reguli:
{*} taie o tabletă în două, tăietura trebuie să fie paralelă cu una din laturile tabletei şi trebuie să nu taie pătrăţelele de ciocolată;

{*} poate să rupă şi să mănânce orice linie sau coloană de pătrăţele care nu se află pe marginea tabletei;
{*} poate să rupă şi să mănânce toate patrăţelele de pe marginea tabletei, cu condiţia ca tableta rămasă să aibă cel puţin dimensiunea $1 x 1$.
Niciuna dintre aceste trei mutări nu poate fi efectuată asupra unei tablete de dimensiune $1 x 1$. Pierde jucătorul care nu mai poate efectua nicio mutare.

{*} pot să rupă şi să mănânce orice linie sau coloană de pătrăţele care nu se află pe marginea tabletei;
{*} pot să rupă şi să mănânce toate patrăţelele de pe marginea tabletei, cu condiţia ca tableta rămasă să aibă cel puţin dimensiunea $1 x 1$.
Niciuna dintre aceste trei mutări nu poate fi efectuată asupra unei tablete de dimensiune $1 x 1$. Pierde jucătorul care nu mai poate efectua nicio mutare. În fişierul de intrare se va afla numărul $N$ ({$1 ≤ N ≤ 100$}) de tablete, iar pe următoarea linie vor fi $N$ perechi de numere întregi care reprezintă dimensiunile tabletelor. În fişierul de ieşire se va afla un singur număr întreg reprezentând numărul mutărilor câştigătoare pentru primul jucător.

h3. Soluţie
Pentru această problemă vom calcula matricea $SG{~i,j~}$ care reprezintă valoarea $Sprague-Grundy$ asociată unei tablete de dimensiuni $(i, j)$. Să vedem care este recurenţa care va satisface elementele matricei $SG$:

TODO start
<tex> SG_{i,j} = mex(SG_{i,k} {\mathbin{\char`\^}} SG_{i,j-k}, (1 \leq k < j) </tex> mutarea întâi
<tex> SG_{k,j} {\mathbin{\char`\^}} SG_{i-k,j}, \hspace{21 mm}(1 \leq k < i) </tex>
<tex> SG_{i,k} {\mathbin{\char`\^}} SG_{i,j-k-1}, \hspace{17.5 mm} (1 \leq k < j - 1) </tex> mutarea a doua
<tex> SG_{k,j} {\mathbin{\char`\^}} SG_{i-k-1,j}, \hspace{17 mm} (1 \leq k < i - 1) </tex>
<tex> SG_{i-2,j-2}) \hspace{28 mm} (i > 2 , j > 2 )</tex> mutarea a treia

<tex> SG_{i,j} = mex( \underbrace{ \underbrace{SG_{i,k} {\mathbin{\char`\^}} SG_{i,j-k},}_{1 \leq k < j} \underbrace{SG_{k,j} {\mathbin{\char`\^}} SG_{i-k,j},}_{1 \leq k < i} }_{mutarea\ \^{i}nt\^{a}i } </tex> <tex> \underbrace{ \underbrace{SG_{i,k} {\mathbin{\char`\^}} SG_{i,j-k-1},}_{1 \leq k < j - 1} \underbrace{SG_{k,j} {\mathbin{\char`\^}} SG_{i-k-1,j},}_{1 \leq k < i - 1} }_{mutarea\ a\ doua} </tex> <tex> \underbrace{ \underbrace{SG_{i-2,j-2}}_{i > 2,\ j > 2} }_{mutarea\ a\ treia} )</tex>

Acum, pentru a calcula numărul de mutări câştigătoare efectuăm asupra fiecărei tablete din fişierul de intrare toate mutările posibile care sunt cel mult de $4 * 100 + 1$ şi facem suma $XOR$ a valorilor $Sprague-Grundy$ pentru restul tabletelor neimplicate în mutare şi a tabletelor rezultate din mutare. Pentru a calcula $SG{~i,j~}$ trebuie sã parcurgem cel mult $2 * i + 2 * j + 1$ valori obţinute. Astfel, algoritmul de determinare al valorilor matricei $SG$ are ordinul de complexitatea $O(N^3^)$. Complexitatea algoritmului care determină numărul de mutări câştigătoare este $O(N^2^)$.

TODO end

h2(#concluzii). Concluzii