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ă;

{*} 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.

{*} 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.

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$:

<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>

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

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