}
==

Am folosit numai trei liste pentru ca am tinut cont de optimizarea precizata mai sus de a nu folosi numai curbele la 0 grade, 45 grade si 90
grade. Fiecare nod poate fi expandat o singura data, si poate fi introdus in liste de cel mult trei ori, deci o astfel de solutie are complexitatea ca timp si ca spatiu O(N*M). Mergand mai departe pe aceasta idee putem obtine o rezolvare putin mai buna care injumatateste timpul de executie. Costurile au fost alese intr-un mod particular permitand ca o curba de 90 de grade sa aiba acelasi cost cu doua curbe de 45, una de 135 acelasi cost ca trei de 45 si una de 180 acelasi cost ca si patru de 45. Astfel putem modifica rezolvarea noastra si sa facem numai miscarile urmatoare: rotiri de 45 de grade pe loc si miscari in fata pe directia de mers. Astfel procedura de expandare actualizeaza numai trei noduri si in cursul procedurii de actualizare putem sa lucram numai cu lista curenta si cu lista urmatoare, pentru ca efectuam numai miscari de cost zero si unu. Aceasta observatie a micsorat numarul de liste si a micsorat numarul de calcule din metoda expand, cea mai frecvent utilizata in algoritm. O astfel de
rezolvare ar fi adus punctajul maxim pe aceasta problema. Mentionam ca toate observatiile facute nu ar fi fost neaparat necesare pentru obtinerea unui punctaj maxim. Testele au fost facute in vederea obtinerii a 50 de puncte folosind cautare in latime simpla, 60-70 de puncte folosind Dijkstra cu heapuri si 90-100 de puncte folosind penultima rezolvare.

Am folosit numai trei liste pentru ca am tinut cont de optimizarea precizata mai sus de a nu folosi numai curbele la $0$ grade, $45$ grade si $90$ grade. Fiecare nod poate fi expandat o singura data, si poate fi introdus in liste de cel mult trei ori, deci o astfel de solutie are complexitatea ca timp si ca spatiu {$O(N*M)$}. Mergand mai departe pe aceasta idee putem obtine o rezolvare putin mai buna care injumatateste timpul de executie. Costurile au fost alese intr-un mod particular permitand ca o curba de $90$ de grade sa aiba acelasi cost cu doua curbe de {$45$}, una de $135$ acelasi cost ca trei de $45$ si una de $180$ acelasi cost ca si patru de {$45$}. Astfel putem modifica rezolvarea noastra si sa facem numai miscarile urmatoare: rotiri de $45$ de grade pe loc si miscari in fata pe directia de mers. Astfel procedura de expandare actualizeaza numai trei noduri si in cursul procedurii de actualizare putem sa lucram numai cu lista curenta si cu lista urmatoare, pentru ca efectuam numai miscari de cost zero si unu. Aceasta observatie a micsorat numarul de liste si a micsorat numarul de calcule din metoda expand, cea mai frecvent utilizata in algoritm. O astfel de rezolvare ar fi adus punctajul maxim pe aceasta problema. Mentionam ca toate observatiile facute nu ar fi fost neaparat necesare pentru obtinerea unui punctaj maxim. Testele au fost facute in vederea obtinerii a $50$ de puncte folosind cautare in latime simpla, $60-70$ de puncte folosind Dijkstra cu heapuri si $90-100$ de puncte folosind penultima rezolvare.
h2. Clasele 11-12
h3. Clasament

Clasele 11-12

==Rankings(rounds="preoni52a" display_entries="7" pager_style="none")==

Clasament

Clasamentul la 11-12 este dominat de echipa ACM care a reusit sa rezolve toate cele 3 probleme (pe unul din cele doua conturi). Este de remarcat faptul ca primii $5$ clasati au punctaje peste $200$ de puncte.

1. Balaurul Arhirel 300 puncte
2. Macarie & Petronela 240 puncte
3. Stanica Andrei 220 puncte
Marin Radu 220 puncte
4. Tiseanu Catalin 215 puncte
Sorin Stancu-Mara 215 puncte
5. Adrian Diaconu 210 puncte
 
Clasamentul la 11-12 este dominat de echipa ACM care a reusit sa rezolve toate cele 3 probleme (pe unul din cele doua conturi). Este de remarcat faptul ca primii 5 clasati au punctaje peste 200 de puncte.
 
Indep

h3. Indep

Problema se poate rezolva in mai multe moduri. Limitele au fost alese astfel incat problema sa fie cat mai usoara. Vom prezenta cele doua solutii pe care le puteti gasi interesante:

Solutia 1

h4. Solutia 1

Prima solutie, si cea mai simpla, utilizeaza principiul programarii dinamice. Se calculeaza numarul de subsiruri din primele i elemente care sunt divizibile cu un numar j intre 1 si 1000. Sa notam acest numar cu Cnt(i, j). Se obtine urmatoare recurenta pentru calculul acestor valori:

Odata calculate aceste valori solutia o vom avea in Cnt(N, 1). Numerele depasesc orice tip de date predefinit si trebuie utilizate numere mari. Limitele fiind destul de mari, folosirea bazei 10 este periculoasa, pe unele teste fiind necesar folosirea bazei 10^9 pentru a reduce timpul de executie. De asemenea si memoria se poate reduce, observand faptul ca pentru a calcula Cnt(i, j) ne sunt necesare doar valorile pentru Cnt(i - 1, k) (ultima doua linii). Complexitatea acestei solutiei va fi O(N * K * L) unde K reprezinta valoarea maxima din sir si L lungimea maxima a numerelor mari.

Solutia 2

h4. Solutia 2

Cea de-a doua solutie, cu mult mai interesanta decat prima, foloseste principiul includerii se excluderii. Fie D(x) multimea numerelor din sir care sunt divizibile cu un anumit numar x, atunci numarul de submultimi formate doar din astfel de numere este Z(x) = 2^card(D(x))-1. Multimile pentru principiul includerii si excluderii sunt chiar D(p), unde p este un numar prim. Intersectia D(p1), D(p2), D(p3).. este D(p1 * p2 * p3...), oarecum evident, pentru p distincte. Rezultatul este de forma: