Tare de tot acest sandbox :)

http://www.infoarena.ro/problema/cifra

h1. Editorial MScex_s1
 
h2. http://www.infoarena.ro/problema/cifra

Rezolvarea de 100 era una mai putin "ortodoxa". La astfel de probleme de obicei incerci brutul si
te bazezi pe niste observatii. Observatia era ca rezultatul cerut se repeta din 100 in 100. Astfel
cu o preprocesare puteam calcula cele 100 valori si erau necesare doar ultimele 2 cifre ale celor
T numere. Complexitate era O(T*L) supraestimat , unde L e lungimea maxima a unui query.

http://www.infoarena.ro/problema/prim

h2. http://www.infoarena.ro/problema/prim

Numarul cerut de problema va fi al K+1-lea numar prim. Cu un ciur cu marime rezonabila ( 2 000 000 )
se poate determina in O(Marime_ciur log log Marime_ciur) ( complexitate aproape liniara ) al K+1-lea
numar prim. Alte solutii in complexitati mai mari ( gen O(N sqrt N) ) puteau lua ceva puncte.

Numarul cerut de problema va fi al K+1-lea numar prim. Cu un ciur cu marime rezonabila ( 2 000 000 ) se poate determina in O(Marime_ciur log log Marime_ciur) ( complexitate aproape liniara ) al K+1-lea numar prim. Alte solutii in complexitati mai mari ( gen O(N sqrt N) ) puteau lua ceva puncte.

http://www.infoarena.ro/problema/fact

h2. http://www.infoarena.ro/problema/fact

Problema asta a fost aleasa ca sa fie cea mai grea din set. Nu necesita decat cunostiinte elementare
si e abordabila pentru un incepator de clasa a 9-a care stie cautare binara.

Problema asta a fost aleasa ca sa fie cea mai grea din set. Nu necesita decat cunostiinte elementare si e abordabila pentru un incepator de clasa a 9-a care stie cautare binara.

Asadar , problema poate fi rezolvata daca o descompunem in 2 subprobleme. Pentru un numar fixat N
cate 0-uri are factorialul acestuia. Un 0 apare de fiecare data cand apare un factor de 2 si un
factor de 5 in descompunerea lui N! . Observatia care ne va ajuta mult este ca un factor de 5
apare mult mai rar decat unul de 2 , deci numarul de 0-uri este determinat de numarul de factori
de 5 din descompunerea numarului.

Asadar , problema poate fi rezolvata daca o descompunem in 2 subprobleme. Pentru un numar fixat N cate 0-uri are factorialul acestuia. Un 0 apare de fiecare data cand apare un factor de 2 si un factor de 5 in descompunerea lui N! . Observatia care ne va ajuta mult este ca un factor de 5 apare mult mai rar decat unul de 2 , deci numarul de 0-uri este determinat de numarul de factori de 5 din descompunerea numarului.

Pentru un N fixat putem numara numerele divizibile cu 5 din N! , lucru care este usor de intuit ca e
 N/5. Dar ce facem cu numerele care au mai multi factori de 5 in decompunere ? ( gen 50 , 125 ) La
fel de usor de intuit e ca numarul de factori de 5 va fi N/5 + N/(5^2) + ...

Pentru un N fixat putem numara numerele divizibile cu 5 din N! , lucru care este usor de intuit ca e N/5. Dar ce facem cu numerele care au mai multi factori de 5 in decompunere ? ( gen 50 , 125 ) La fel de usor de intuit e ca numarul de factori de 5 va fi N/5 + N/(5^2) + ...

Acum avem pentru un numar N fixat numarul de 0-uri din descompunerea lui. Numarul cu P zerouri poate
fi cautat binar. Complexitate finala va fi astfel O( log^2 N ).

Acum avem pentru un numar N fixat numarul de 0-uri din descompunerea lui. Numarul cu P zerouri poate fi cautat binar. Complexitate finala va fi astfel
O( log^2 N ).