Pentru a 2-a cerinta incercam sa construim a {$K$}-a secventa lexicografica de la inceput catre sfarsit. Astfel, la fiecare pas incercam sa punem o segventa de tipul '{$0...01$}' care sa contina un numar maxim de '{$0$}'. Daca la pasul curent nu putem pune nici un '{$0$}' atunci vom pune o secventa de tipul '{$1..1$}' care sa contina un numar minim de {$1$}. Numarul de '{$0$}'-uri sau de '{$1$}' pe care il punem il vom calcula cu ajutorul matricei precalculate la prima cerinta. Astfel, daca putem pune $p$ de '{$0$}' inseamna ca numarul de posibilitati pentru a completa restul solutiei daca punem cel putin $p$ de '{$0$}' la inceput este mai mare sau egal cu {$K$}. Alegem cel mai mare numar $p$ cu proprietatea de mai sus. Daca $p$ nu exista, incercam sa punem cat mai putini '{$1$}' in aceeasi maniera. Continuam apoi cu restul secventei, iar din $K$ scadem numarul de solutii peste care am "sarit".
Tare de tot acest sandbox :)

 
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
 
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
 
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 ).