O problema aparent simpla.. Dar stati.. Nu putem sa precalculam raspunsurile pentru ca nu avem destula memorie. Nu putem sa raspundem offline la query-uri pentru ca avem nevoie de raspunsul de la ultimul query pentru a-l genera pe urmatorul. Ce este de facut ?

Avem foarte mult timp la dispozitie. Nu ne permitem ca pentru un query q sa pornim de la t=0 si sa urmam recurenta pana la t=q. Ce ne permitem in schimb este sa calculam la inceput valorile pana la pasul 10^7^ si sa retinem doar in anumite locuri rezultatul. Putem sa pornim cautarea atunci de la cel mai apropiat punct inainte de q. Vom retine evident rezultatul la puncte echidistante. Daca retinem rezultatul din <tex>{\sqrt{M}}</tex> in <tex>{\sqrt{M}}</tex> producem o balansare intre timp si memorie. Complexitatea finala va fi <tex>O(M + Q*{\sqrt{M}})</tex> ca timp si <tex>O({\sqrt{M}})</tex> ca memorie. Limita de memorie ne permite si mai mult. Cu cat gap-ul dintre punctele precalculate este mai mic, cu atat solutia va fi mai rapida.

Avem foarte mult timp la dispozitie. Nu ne permitem ca pentru un query q sa pornim de la t=0 si sa urmam recurenta pana la t=q. Ce ne permitem in schimb este sa calculam la inceput valorile pana la pasul 10^7^ + 3 si sa retinem doar in anumite locuri rezultatul. Putem sa pornim cautarea atunci de la cel mai apropiat punct inainte de q. Vom retine evident rezultatul la puncte echidistante. Daca retinem rezultatul din <tex>{\sqrt{M}}</tex> in <tex>{\sqrt{M}}</tex> producem o balansare intre timp si memorie. Complexitatea finala va fi <tex>O(M + Q*{\sqrt{M}})</tex> ca timp si <tex>O({\sqrt{M}})</tex> ca memorie. Limita de memorie ne permite si mai mult. Cu cat gap-ul dintre punctele precalculate este mai mic, cu atat solutia va fi mai rapida.

==include(page="onis-2015/solutii-runda-1/semipal")==