h1(#cmmdcgame). 'Solutia':winter-challenge-2020/solutii/cmmdcgame problemei 'Cmmdcgame':problema/cmmdcgame

Solutia va fi postata in curand.

Cunostinte necesare: teorema Sprague-Grundy, nimber-uri. Autorul problemei recomanda "acest tutorial":https://cp-algorithms.com/game_theory/sprague-grundy-nim.html

Iata cuvinte cheie: Sprague-Grundy, numere prime.

Conform teoremei Sprague-Grundy, jocul din enunt se poate reduce la un joc de nim pe o singura gramada ({$nimber$}-ul jocului). Cum adunarea pe $nimber$-uri corespunde operatiei $XOR$, si suma a doua jocuri, in acest sens, este jocul ce rezulta prin jocul in paralel a celor doua jocuri, se poate arata ca este suficient sa calculam $nimber$-ul fiecarei gramezi (oras, in enunt), apoi sa calculam $XOR$-ul lor, si apoi sa vedem daca rezultatul este 0 (in care caz castiga al doilea jucator) sau nu (in care caz castiga primul jucator).
 
Care este $nimber$-ul unei gramezi (oras)? Stim ca $nimber$-ul unei stari dintr-un joc este egal cu cel mai mic $nimber$ la care nu putem ajunge printr-o mutare din acea stare. Mai intai sa ne gandim la $nimber$-ul unei gramezi de marime prima (sau $1$). Din aceasta stare putem sa mergem in oricare marime mai mica de gramada -- inclusiv toate marimile prime (sau $1$) mai mici. Asta implica ca numerele prime (si $1$) au $nimber$-uri strict crescatoare. Ba chiar, daca jocul ar permite sa mergem doar prin gramezi de marime prima (sau $1$), atunci $1$ ar avea $nimber$-ul $0$, $2$ $nimber$-ul $1$, $3$ $nimber$-ul $2$, $5$ $nimber$-ul $3$, $7$ $nimber$-ul $4$ si asa mai departe. Sa presupunem pe moment ca aceste atribuiri de $nimber$-uri sunt corecte. Care ar fi atunci $nimber$-ul unui numar compus? Este clar ca dintr-un numar compus putem muta in toate numerele prime (si $1$) mai mici ca cel mai mic factor prim al numarului nostru. Totodata nu putem muta in niciun numar care impartaseste acest factor prim minim (ca acel numar ar fi necoprim cu numarul actual). Asta ne arata ca $nimber$-ul unui numar compus este egal cu $nimber$-ul celui mai mic factor prim al numarului (acest fapt se poate demonstra riguros prin inductie).
 
Astfel, concret, pentru a rezolva problema, calculam, cu ajutorul unui ciur (analog cu ciurul lui Eratostene), pentru fiecare marime posibila de oras, valoarea $f(x)$, egala cu cel mai mic factor prim al lui $x$, respectiv $i(x)$, egala cu indicele lui $x$ ca numar prim (sau $1$), adica $i(1) = 0, i(2) = 1, i(3) = 2, i(5) = 3, i(7) = 4$, etc. Atunci, calculam $XOR$-ul valorilor $i(f(x))$ pentru toate marimile $x$ de orase, si afisam ca primul jucator (adica Daenarys) castiga daca si numai daca aceasta valoare este nenula.