Desi s-a desfasurat intr-o zi de miercuri, runda a doua a concursului preONI a avut un numar aproape dublu de accesari fata de runda 1. Acest lucru se datoreaza probabil atat faptului ca olimpiada judeteana "bate la usa" cat si prezentei premiilor oferite de sponsorul nostru, Microsoft Romania.

In continuarea acestui articol vom descrie solutiile oficiale ale problemelor. Daca aveti nelamuriri puteti sa puneti intrebari pe "forum":http://forum.infoarena.ro/.

In continuarea acestui articol vom descrie solutiile oficiale ale problemelor. Daca aveti nelamuriri puteti sa puneti intrebari pe "forum":http://infoarena.ro/forum.

Scopul principal al concursului preONI 2005 este antrenamentul pentru ONI. Nivelul problemelor a fost corespunzator, asa ca nu fiti descurajati la OJI daca n-ati facut foarte bine acum! ;)

h3. Pascal

Ca sa calculam puterea la care apare factorul prim $p$ in descompunerea lui $n!$ se poate folosi urmatoare formula $f = [n/p] + [n/p^2^] + [n/p^3^] +$ ... ({$[]$} reprezinta partea intrega). Avand acesta formula putem traversa un anumit rand din triunghiul lui Pascal si pt fiecare element ({$r,c$}) putem calcula puterea la care apare $d$ in descompunerea lui $r ! / ((r-c) ! * c!)$ . Atunci cand $d$ nu este prim trebuie sa avem grija sa verificam daca respectivul element ({$r,c$}) are in descompunerea sa toti factori primi a lui {$d$}. Daca $d=6$ , elementul din ({$r,c$}) trebuie sa contina $2$ si $3$ in descompunerea sa, iar daca {$d = 4$}, trebuie sa contina $2$ de cel putin doua ori.

Ca sa calculam puterea la care apare factorul prim $p$ in descompunerea lui $n!$ se poate folosi urmatoare formula $f = [n/p] + [n/p^2^] + [n/p^3^] +$ ... ({$[]$} reprezinta partea intrega). Avand acesta formula putem traversa un anumit rand din triunghiul lui Pascal si pt fiecare element ({$r,c$}) putem calcula puterea la care apare $d$ in descompunerea lui $r! / ((r-c)! * c!)$ . Atunci cand $d$ nu este prim trebuie sa avem grija sa verificam daca respectivul element ({$r,c$}) are in descompunerea sa toti factori primi a lui {$d$}. Daca $d = 6$ , elementul din ({$r,c$}) trebuie sa contina $2$ si $3$ in descompunerea sa, iar daca {$d = 4$}, trebuie sa contina $2$ de cel putin doua ori.

O alta modalitate sa calculam puterea la care apare un factor prim $p$ in descompunerea lui este: fie {$A{~c~}$} = puterea la care apare $p$ in decompunrea lui ({$r,c$}). $A{~c+1~}$ = {$A{~c~}$} + puterea lui $p$ in ({$r-c$}) - puterea lui $p$ in ({$c+1$}). Acesta relatie se poate deduce din modul din care putem calcula elementul ({$r,c+1$}) din ({$r,c$}) folosind formula ({$r,c$}) = $r ! / ((r-c)! * c !)$

O alta modalitate sa calculam puterea la care apare un factor prim $p$ in descompunerea lui este: fie {$A{~c~}$} = puterea la care apare $p$ in decompunerea lui ({$r,c$}). $A{~c+1~}$ = {$A{~c~}$} + puterea lui $p$ in ({$r-c$}) - puterea lui $p$ in ({$c+1$}). Acesta relatie se poate deduce din modul din care putem calcula elementul ({$r,c+1$}) din ({$r,c$}) folosind formula ({$r,c$}) = $r! / ((r-c)! * c!)$

Aceasta a fost cea mai simpla problema de la clasele {$9-10$}, oricare din cele doua idei prezentate mai sus aducand punctaj maxim.

h3. Clasament

==Rankings(rounds="preoni52a" display_entries="7" pager_style="none")==

==Rankings(rounds="preoni52b" display_entries="7" pager_style="none")==

Clasamentul la 11-12 este dominat de echipa ACM care a reusit sa rezolve toate cele 3 probleme (pe unul din cele doua conturi). Este de remarcat faptul ca primii $5$ clasati au punctaje peste $200$ de puncte.

== code(cpp) |Cnt[i][cmmdc(j, A[i])] = Cnt[i - 1][j] + Cnt[i - 1][cmmdc(j, A[i])]
==

Odata calculate aceste valori solutia o vom avea in {$Cnt{@[@}N{@][@}1{@]@}$}. Numerele depasesc orice tip de date predefinit si trebuie utilizate numere mari. Limitele fiind destul de mari, folosirea bazei $10$ este periculoasa, pe unele teste fiind necesar folosirea bazei $10^9^$ pentru a reduce timpul de executie. De asemenea si memoria se poate reduce, observand faptul ca pentru a calcula {$Cnt{@[@}i{@][@}j{@]@}$} ne sunt necesare doar valorile pentru {$Cnt{@[@}i-1{@][@}k{@]@}$} (ultima doua linii). Complexitatea acestei solutiei va fi $O(N * K * L)$ unde $K$ reprezinta valoarea maxima din sir si $L$ lungimea maxima a numerelor mari.

Odata calculate aceste valori solutia o vom avea in {$Cnt{@[@}N{@][@}1{@]@}$}. Numerele depasesc orice tip de date predefinit si trebuie utilizate numere mari. Limitele fiind destul de mari, folosirea bazei $10$ este periculoasa, pe unele teste fiind necesar folosirea bazei $10^9^$ pentru a reduce timpul de executie. De asemenea si memoria se poate reduce, observand faptul ca pentru a calcula {$Cnt{@[@}i{@][@}j{@]@}$} ne sunt necesare doar valorile pentru {$Cnt{@[@}i-1{@][@}k{@]@}$} (ultimele doua linii). Complexitatea acestei solutiei va fi $O(N * K * L)$ unde $K$ reprezinta valoarea maxima din sir si $L$ lungimea maxima a numerelor mari.

h4. Solutia 2

h3. Cerere

Problema este de dificultate medie. O rezolvare $O(N*lg(N))$ este usor de gasit, fiind asemanatoare cu una deja exista in arhiva, "Stramosi":http://www.infoarena.ro/task/stramosi. Dar o astfel de rezolvare n-ar fi adus punctaj maxim in mod normal. Problema se poate rezolva printr-o simpla parcurgere in adancime din radacina implementand manual stiva DF-ului. Cand vom pune un nod $n$ pe pozitia $p$ in stiva, al {$K$}-lea stramos va fi nodul de pe pozitia $p-K$ din stiva, pentru care s-a procesat deja valoarea ceruta. Complexitatea finala a algoritmului va fi {$O(N)$}.

Problema este de dificultate medie. O rezolvare $O(N*lg(N))$ este usor de gasit, fiind asemanatoare cu una deja exista in arhiva, "Stramosi":http://infoarena.ro/problema/stramosi. Dar o astfel de rezolvare n-ar fi adus punctaj maxim in mod normal. Problema se poate rezolva printr-o simpla parcurgere in adancime din radacina implementand manual stiva DF-ului. Cand vom pune un nod $n$ pe pozitia $p$ in stiva, al {$K$}-lea stramos va fi nodul de pe pozitia $p-K$ din stiva, pentru care s-a procesat deja valoarea ceruta. Complexitatea finala a algoritmului va fi {$O(N)$}.

h3. Rubarba