Pagini recente » Monitorul de evaluare | Profil iuli_morariu | Monitorul de evaluare | Concursuri Virtuale | Diferente pentru onis-2015/solutii-runda-1 intre reviziile 97 si 98
Nu exista diferente intre titluri.
Diferente intre continut:
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.
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 ≤ N cel putin unul dintre a si b este ≤ <tex>{\sqrt{N}}</tex> Putem sa calculam cu formula de mai sus sol = nr. de perechi in care stangacia fetelor este ≤ <tex>{\sqrt{N}}</tex>. Atunci tot acesta va fi numarul de perechi in care stangacia baietilor este ≤ <tex>{\sqrt{N}}</tex>. Atunci raspunsul final = 2*sol - @cate perechi exista in care atat stangacia fetelor cat si a baietilor este@ ≤ <tex>{\sqrt{N}}</tex>. Acesta din urma este chiar [<tex>{\sqrt{N}}</tex>]^2
O solutie mult mai simpla si mai rapida este sa ne dam seama ca intr-o pereche (a,b) cu a*b ≤ N cel putin unul dintre a si b este ≤ <tex>{\sqrt{N}}</tex> Putem sa calculam cu formula de mai sus sol = nr. de perechi in care stangacia fetelor este ≤ <tex>{\sqrt{N}}</tex>. Atunci tot acesta va fi numarul de perechi in care stangacia baietilor este ≤ <tex>{\sqrt{N}}</tex>. Atunci raspunsul final = 2*sol - @cate perechi exista in care atat stangacia fetelor cat si a baietilor este@ ≤ <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.
Dandu-se un sir de numere, care este lungimea celui mai lung subsir alternant ? este intrebarea pusa de aceasta problema.
Dificultatea acestei probleme consta in a face urmatoarea constatare:
* Consideram toate solutiile pentru care avem cel mult un element pe fiecare secventa de monotonie: atunci evident sol ≤ 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 ≤ S+1 = V
* Consideram toate solutiile pentru care avem cel putin o secventa de monotonie cu trei elemente: Nu exista
* Consideram toate solutiile pentru care avem cel putin o secventa de monotonie cu trei elemente: Nu exista.
Atunci sol ≤ V oricare ar fi sol - lungimea unui sir alternant. Atunci V este valoarea maxima a lungimii unui subsir alternant.
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.
