Tare de tot acest sandbox :)

h2. Editorial MScex shortround #1
 
( autor ==user(user="danalex97" type="tiny")== )
 
h4. 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.
 
h4. 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.
 
h4. 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.
 
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) + ...
 
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 ).