Folosind aceste valori, vom determina bitii celui de-al $M$-lea sir, unul cate unul, pornind de la al $N$-lea bit. La fiecare pas, va trebui sa determinam cate siruri incep cu bitul $0$ si cate siruri incep cu bitul $1$. La inceput, vor exista $num[N-1,3]$ siruri care incep cu bitul $0$ si $num[N-1,2]$ siruri care incep cu bitul $1$. Este evident ca, la un anumit pas, toate sirurile care incep cu $0$ se vor afla inaintea tuturor sirurilor care incep cu $1$. De aceea, daca $M$ < numarul sirurilor care incep cu $0$, bitul respectiv va fi $0$; in caz contrar, bitul va fi $1$. Daca bitul este $1$, inainte de a trece la pasul urmator, va trebui sa actualizam valoarea lui $M$, in asa fel incat sa sarim peste toate sirurile care incep cu $0$ ({$M = M - numarul de siruri care incep cu 0$), precum si sa tinem cont de faptul ca am mai consumat inca un bit de $1$. Algoritmul in pseudocod este urmatorul:

== code(c) |
nrbiti = 3

== code(c) | nrbiti = 3

for i = N -> 1
  daca num[i-1, nrbiti] >= M atunci
    bitul i este 0

* $K=1$: Daca $N$ este impar, atunci primul jucator castiga; in caz contrar, al doilea jucator castiga.
* $K > 1$: Pentru $K > 1$, va trebui sa folosim teoria numerelor Grundy (vezi 'link1':http://www.ginfo.ro/revista/14_5/mate.pdf , 'link2':http://en.wikipedia.org/wiki/Sprague-Grundy_theory , 'link3':http://yucs.org/~gnivasch/cgames/spraguegrundy/index.html ). Vom calcula pentru fiecare $i$ de la $1$ la $3000$ o valoarea $grundy[i]$, reprezentand numarul Grundy corespunzator unei table formate din $i$ patratele. Pentru $0 ≤ i ≤ K-1$, $grundy[i]=0$. Pentru $i ≥ K$, vom genera toate starile in care putem ajunge dupa prima mutare efectuata: $S{~j~}$ $(0 ≤ j ≤ i-K)$ - plasam piesa pe patratelele $j+1,..,j+K$, impartind tabla in $2$ bucati, una de dimensiune $j$, alta de dimensiune $i-j-K$; calculam apoi numarul Grundy asociat acestei stari "compuse", ca fiind $grundy_compus[S{~j~}] = grundy[j] *xor* grundy[i-j-K]$. Vom calcula apoi primul numar natural (mai mare sau egal cu $0$) care nu apare in multimea numerelor $grundy_compus[S{~j~}]$. Aceasta valoare corespunde numarului $grundy[i]$ (pe care doream sa-l calculam). Pentru o dimensiune $i$ a tablei, jucatorul $1$ are strategie sigura de castig daca $grundy[i] > 0$; in caz contrar, va avea strategie sigura de castig jucatorul $2$. Este evident ca, pentru o valoare $M$, putem calcula numerele Grundy pentru dimensiuni ale tablei de la $1$ la $M$ in complexitate $O(M^2^)$. Dupa ce calculam aceste valori, va trebui sa observam niste reguli pentru a putea rezolva problema pentru limitele date:

** $K > 2$ si $max{3000, 69*K-19} = 3000$: Pentru acest caz nu trebuie sa facem nimic special. Pur si simplu calculam numerele Grundy conform algoritmului descris mai sus si, pentru fiecare test, raspundem in complexitate $O(1)$.
** $K > 2$ si $max{3000, 69*K-19} = 69*K-19$: Dimensiunile tablei de la $1$ la $K-1$ sunt pierzatoare pentru primul jucator, iar dimensiunea $K$ este castigatoare. Vom observa ca, dupa dimensiunea $K-1$, exista $12$ stari pierzatoare pentru primul jucator, de forma $a*K+b$, care sunt aceleasi indiferent de $K$ (in sensul ca sunt aceleasi constante $a$ si $b$). Cel mai simplu mod de a observa acest lucru este de a afisa diferenta dintre dimensiunea $X$ a tablei corespunzatoare unei stari pierzatoare si dimensiunea $Y$ a tablei anterioare ce corespunde unei stari pierzatoare. Cele $12$ diferente sunt, in ordine: $2*K$, $2*K$, $4*K-2$, $4*K-2$, $4*K$, $4*K-2$, $8*K-2$, $4*K-2$, $8*K$, $8*K-2$, $16*K-6$, $4*K$ . Aceasta regula este valida pentru $K ≥ 4$ (dar noi o vom folosi doar pentru $K ≥ 44$, deoarece pentru $K < 44$, ne vom afla in cazul anterior).
** $K=2$: In acest caz ne vom uita, din nou, la diferentele dintre doua stari pierzatoare (pentru primul jucator) consecutive. Vom observa ca sirul acestor diferente (considerand prima stare pierzatoare "interesanta" ca fiind $K-1$) consta dintr-un prefix de lungime $8$ $(4,4,6,6,4,4,6,4)$, dupa care sirul devine periodic, cu perioada $5$ $(4,12,4,4,10)$.