Observam ca, pentru ca media aritmetica a doua numere sa fie un numar intreg, ambele numere trebuie sa aiba aceeasi paritate. Acesta observatie ne-ar putea conduce la ideea de a separa, in cadrul permutarii, numerele pare de numerele impare. Sa presupunem ca vrem sa amplasam la inceputul permutarii toate numerele pare, apoi toate numerele impare. Sa consideram cazul numerelor pare, cazul numerelor impare tratandu-se similar. Avem $N/2$ numere pare: $2, 4, 6, ...$ pe care trebuie sa le ordonam in asa fel incat media aritmetica a oricare doua numere sa nu se afle intre ele. Vom renumerota numerele pare ca fiind $1, 2, .., N/2$ si vom observa ca acum problema s-a redus la a gasi o permutare de $N/2$ elemente pentru care media a oricare $2$ numere sa nu se afle intre ele (exact problema initiala, dar pentru $N$ injumatatit). Vom aplica in mod recursiv acest algoritm, pana ajungem la permutari cu $1$ sau $2$ elemente.
Daca aplicam algoritmul direct, obtinem o solutie de tipul 'Divide et Impera':http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm , ce are complexitatea $O(N*logN)$. O imbuntataire a acestei solutii (care nu este necesara pentru a obtine punctajul maxim la problema) consta in observatia ca, de fapt, va trebui sa rezolvam cel mult $2*logN$ probleme distincte. Sa consideram urmatorul caz (cea mai proasta situatie):

* $N=2*k+1$: La primul nivel de recursivitate trebuie sa rezolvam problema pentru valorile k si k+1. Avem urmatoarele $2$ subcazuri:
** $k=2*p$ si $k+1=2*p+1$: Pentru $k$, va trebui sa rezolvam la nivelul urmator de recursivitate problema pentru valoarea $p$, iar pentru $k+1$ va trebui sa rezolvam problema pentru valorile $p si p+1$ ; asadar, la urmatorul nivel de recursivitate va trebui sa rezolvam problema doar pentru valorile distincte $p$ si $p+1$.
** $k=2*p-1$ si $k+1=2*p$: Pentru $k$, va trebui sa rezolvam la nivelul urmator de recursivitate problema pentru valorile $p-1$ si $p$, iar pentru $k+1$ va trebui sa rezolvam problema pentru valoarea $p$ ; asadar, la urmatorul nivel de recursivitate va trebui sa rezolvam problema doar pentru valorile distincte $p-1$ si $p$.

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