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

Daca un baiat are stangacia x, atunci numarul de fete cu care poate dansa este [n/x].
Deci trebuie sa calculam [n/1] + [n/2] + [n/3] + ... + [n/n].
Ne permitem sa calculam suma pana la <tex>{\sqrt{N}}</tex>. De acolo putem constata ca exista <tex>{\sqrt{N}}</tex> intervale de numere, pe un interval toate numerele i avand acelasi rezultat al expresiei [n/i]. putem sa aflam primul si ultimul numar din intervalul care il are ca rezulatat al expresiei pe rez: acestea sunt n/(rez-1) + 1 si n/rez.
 
O solutie mult mai simpla si mai rapida este sa ne dam seama ca intr-o pereche (a,b) cu a*b &le; N cel putin unul dintre a si b este &le; <tex>{\sqrt{N}}</tex> Putem sa calculam cu formula de mai sus sol = nr. de perechi in care stangacia fetelor este &le; <tex>{\sqrt{N}}</tex>. Atunci tot acesta va fi numarul de perechi in care stangacia baietilor este &le; <tex>{\sqrt{N}}</tex>. Atunci raspunsul final = 2*sol - @cate perechi exista in care atat stangacia fetelor cat si a baietilor este@ &le; <tex>{\sqrt{N}}</tex>. Acesta din urma este chiar [<tex>{\sqrt{N}}</tex>]^2
 
Complexitatea este <tex>O({\sqrt{N}})</tex>
 

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

Dandu-se un sir de numere, care este cel mai lung subsir alternant ? este intrebarea pusa de aceasta problema.
 
Dificultatea acestei probleme consta in a face urmatoarea constatare:
 
* Valoarea celui mai lung subsir alternant este data de numarul de 'varfuri' din sir:
 
Un varf este un element @v[i]@ pentru care se intampla una din urmatoarele
 
* @v[i-1] < v[i] > v[i+1]@
* @v[i-1] > v[i] < v[i+1]@
* @v[i] este primul element, i = 1
* @v[i] este ultimul element, i = N
 
Aceste modificari pot fi suportate in <tex>O(1)</tex> pe query. Pur si simplu verificam daca elementul curent sau vecinii lui au devenit sau au decazut din statutul de varf.
 
Complexitate <tex>O(N + M)</tex>
 
Demonstratie: Vom considera sirul divizat in 'secvente de monotonie'. Doua secvente de monotonie consecutive sunt legate printr-un varf (care apartine amandurora). Fie V = numarul de varfuri si S = numarul de secvente de monotonie. Are loc relatia V = S-1.
 
* Consideram toate solutiile pentru care avem cel mult un element pe fiecare secventa de monotonie: atunci evident sol &le; S < V.
* Consideram toate solutiile pentru care avem cel putin o secventa de monotonie cu doua elemente. Daca alegem o secventa de monotonie pe care alegem doua elemente, pe restul secventelor este imposibil sa alegem doua si vom alege cel mult 1, atunci sol &le; S+1 = V
* Consideram toate solutiile pentru care avem cel putin o secventa de monotonie cu trei elemente: Nu exista
 
Atunci sol &le; V oricare ar fi sol - lungimea unui sir alternant. Atunci V este valoarea maxima a lungimii unui subsir alternant.
 
 
O problema aparent simpla.. Dar stai.. 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 la query-ul anterior pentru a-l genera pe urmatorul. Ce este de facut ?
 
 
 

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