<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^)$.

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 $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 a valorilor matricei $SG$ are ordinul de complexitate $O(N^3^)$. Complexitatea algoritmului care determină numărul de mutări câştigătoare este $O(N^2^)$.

h2(#concluzii). Concluzii

* Thomas S. Ferguson - 'Game Theory Text':http://www.math.ucla.edu/~tom/gamescourse.html
* 'Interactive Mathematics':http://www.cut-the-knot.com
* 'Wolfram MathWorld':http://www.mathworld.wolfram.com

* 'IPSC':http://ipsc.ksp.sk/

* 'IPSC':http://ipsc.ksp.sk/
 
h2. Discuţii pe forum