Aceasta problema a fost considerata cea mai simpla din concurs, in special pentru ca realizarea unui program experimental care simula pasii din problema ne arata ca usile ce raman inchise au ca index un patrat perfect.

Pentru a demonstra aceasta afirmatie avem nevie de cateva cunostinte minore de teoria numerelor.

Pentru a demonstra aceasta afirmatie avem nevoie de cateva cunostinte minore de teoria numerelor.

La fiecare pas $i$ directorul va vizita toti multiplii lui {$i$}, ceea ce inseamna ca un anumit numar $X4 va fi vizitat la pasii ai caror indecsi il divid pe {$X$}. Deci pentru a afla cate usi vor fi deschise in final va trebui sa numaram cate numere au un numar par de divizori. Pentru acest lucru ne va si mai usor sa numaram cate au un numar impar de divizori urmand sa le scadem din {$N$}. Stim ca daca descompunem un numar $X$ in factori primi: {$X=F{~1~}^P{~1~}^*F{~2~}^P{~2~}^*...*F{~t~}^P{~t~}^$} numarul de divizori ai sai va fi {$D=(P{~1~}+1)*(P{~2~}+1)*...*(P{~t~}+1)$}. Pentru ca $D$ sa fie impar trebuie ca fiecare factor al produsului sa fie deci $P{~i~}+1$ impar ceea ce inseamna ca exponentii factorilor primi din descompunere vor fi pari. {$X=F{~1~}^2*P'{~1~}^*F{~2~}^2*P'{~2~}^*...*F{~t~}^2*P'{~t~}^ = (F{~1~}^P'{~1~}^*F{~2~}^P'{~2~}^*...*F{~t~}^P'{~t~}^)^2^$}. Inseamna ca $X$ va fi patrat pefrect.

Acum daca vrem sa calculam $LUNG{~9~}$ ar trebui sa ne extindem cat putem in lateral fata de {$b$}, dar observam ca centrul palindromului curent este continut in palindromul centrat la {$6$}. Din faptul ca palindromul contine doua subsecvente oglindite, noi nu trebuie sa mai iteram prin literele palindromului nostru pentru ca avem deja rezolvata problema oglindita, si continuam comparatiile cu caractere noi (in cazul nostru avem deja rezolvata problema {$a b a$} in secventa [{$1..5$}] si nu mai trebuie sa o rezolvam inca o data). Am obtinut astfel o rezolvare simpla de complexitate {$O(N)$}. Mentionam ca sursa oficiala nu are mai mult de $50$ de linii.

Exista si alte rezolvari optime posibile si ii rugam pe cei care au luat $100$ de puncte sa le explice in cadrul "forumului":http://forum.infoarena.ro/index.php/board,25.0.html.

Exista si alte rezolvari optime posibile si ii rugam pe cei care au luat $100$ de puncte sa le explice in cadrul "forumului":http://infoarena.ro/forum/index.php/board,25.0.html.