Diferente pentru preoni-2006/runda-4/solutii intre reviziile #24 si #27

Nu exista diferente intre titluri.

Diferente intre continut:

Una peste alta, s-a incheiat o etapa frumoasa a concursului in care am pus mult suflet. Normal, pot fi doar 30 de participanti fericiti de rezultate. Ii felicitam pe cei calificati si abia asteptam sa-i vedem in finala. Ii felicitam si pe ceilalti care nu au putut sa-si tina suflul pana in final, pierzand locurile calificabile. Noi le uram cat mai multe succese, sa mai alerge vreo cateva sute de probleme (incepand cu cele din Arhiva noastra) si sa ne intalnim cu ei mult mai pregatiti la startul urmatorului preONI.
In urmatoarele pagini vom incerca sa explicam solutiile problemelor. Asa cum v-ati obisnuit, va puteti lamuri orice vi se pare neclar sau vag explicat intreband pe "forum":http://forum.infoarena.ro/, unde vom incerca sa raspundem cat mai promt. Va asteptam cu intrebari si sugestii (asigurati-va ca pareririle va sunt auzite!)
In urmatoarele pagini vom incerca sa explicam solutiile problemelor. Asa cum v-ati obisnuit, va puteti lamuri orice vi se pare neclar sau vag explicat intreband pe "forum":http://forum.infoarena.ro/, unde vom incerca sa raspundem cat mai prompt. Va asteptam cu intrebari si sugestii (asigurati-va ca pareririle va sunt auzite!)
h2. NextSeq
(problema simpla clasa a 9-a)
$A = T{~1~}^R1 * Q^ * ... * T{~K~}^RK * Q^$
Al doilea pas este sa observam ca daca aflam pentru fiecare $T{~i~}$, $B{~i~}$ astfel incat $B{~i~}!$ se divide la $T{~i~}^Ri * Q^$ atunci $B$ (numarul cautat in problema) este maximul dintre $B{~i~}$. Implicatia imediata e ca putem sa ne ocupam de fiecare numar prim in parte fara sa tinem cont de celelalte.
Al treilea pas consta in determinarea $B{~i~}$-urilor cu ajutorul cautarii binare. Pentru o valoare candidata $X$ (din cautarea binara) trebuie sa calculam puterea lui $T{~i~}$ in descompunerea lui $X!$. Acest lucru se afla simplu ca fiind $[X/T{~i~}] + [X/T{~i~}^2^] + ...$ (unde prin $[x]$ intelegem partea intreaga a lui $x$). Cautarea binara se poate optimiza observand ca $B{~i~}$ este intotdeauna divizibil cu $T{~i~}$, ba mai mult nu va fi mai mare decat $(R{~i~} * Q) * T{~i~}$ (observatie necesara obtinerii punctajului maxim). In concluzie, vom cauta binar o valoare intreaga $K$ in intervalul $[1, R{~i~} * Q]$ astfel incat $B{~i~} = K * T{~i~}$ sa aiba propietata ca $B{~i~}!$ se divide la $T{~i~}^Ri * Q^$. Va puteti intreba de ce putem cauta binar. Este simplu: daca o valoare $X$ are propietatea ca $X!$ se divide la $Y$ (unde lui $X$ si $Y$ le putem da semnificatiile dorite de noi) atunci, evident, si $(X + 1)!$ se divide la $Y$.
Al treilea pas consta in determinarea $B{~i~}$-urilor cu ajutorul cautarii binare. Pentru o valoare candidata $X$ (din cautarea binara) trebuie sa calculam puterea lui $T{~i~}$ in descompunerea lui $X!$. Acest lucru se afla simplu ca fiind $[X/T{~i~}] + [X/T{~i~}^2^] + ...$ (unde prin $[x]$ intelegem partea intreaga a lui $x$). Cautarea binara se poate optimiza observand ca $B{~i~}$ este intotdeauna divizibil cu $T{~i~}$, ba mai mult nu va fi mai mare decat $(R{~i~} * Q) * T{~i~}$ (observatie necesara obtinerii punctajului maxim). In concluzie, vom cauta binar o valoare intreaga $K$ in intervalul $[1, R{~i~} * Q]$ astfel incat $B{~i~} = K * T{~i~}$ sa aiba propietatea ca $B{~i~}!$ se divide la $T{~i~}^Ri * Q^$. Va puteti intreba de ce putem cauta binar. Este simplu: daca o valoare $X$ are propietatea ca $X!$ se divide la $Y$ (unde lui $X$ si $Y$ le putem da semnificatiile dorite de noi) atunci, evident, si $(X + 1)!$ se divide la $Y$.
Solutia finala va avea complexitatea $O(√P * log Q * log Q)$. Exista o serie de solutii intermediare care permiteau obtinerea de punctaje suficient de mari si de aceea problema a fost considerata medie desi rezolvarea completa este destul de dificila.

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.