Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-01-21 14:16:00.
Revizia anterioară   Revizia următoare  

Runda 1

  • scuzele de rigoare referitoare la inregistrarea
  • cometarii despre clasament

Aprindere

(problema usoara, clasa a 9-a)

Este evident ca nu are rost sa actionam un intrerupator de mai multe ori. In aceste conditii, solutia este unica, deoarece nu putem avea doua intrerupatoare intr-o singura camera. Cu alte cuvinte, daca parcurgem camerele de la stanga la dreapta si intalnim o camera cu becul inchis, va trebui sa actionam intrerupatorul unic din camera respectiva. Daca am fi permis ca o camera sa aiba mai multe intrerupatoare, problema s-ar fi complicat semnificativ.
Se pot afla usor intrerupatoarele care trebuie actionate astfel: se parcurg camerele de la stanga la dreapta, iar in momentul in care ajungem la o camera cu becul inchis trebuie sa actionam intrerupatorul din camera respectiva (daca nu exista intrerupator, atunci nu avem solutie). Cum intrerupatorul respectiv actioneaza becuri din camere ≥ i, nu vom modifica nimic din becurile precedente. De asemenea, vom aduna costul lor la rezultat.

Patrate3

(problema medie, clasa a 9-a)

Mai intai sortam punctele crescator dupa abscisa, iar pentru abscise egale dupa ordonata. Acum, folosind cautarea binara putem cauta orice punct in timp logaritmic. Pentru fiecare pereche de puncte vom forma patratul care are o diagonala formata din perechea respectiva. Dupa ce calculam si celelalte 2 puncte, le cautam binar in vectorul sortat. Daca le gasim, inseamna ca am mai gasit un patrat. Complexitatea solutiei este O(N2 log N). Precizia recomandata este de 10-4.

Elimin

(problema grea, clasa a 9-a / problema medie, clasa a 10-a)

Daca S este suprafata ( aria ) matricii, este evident ca minim(M, N) ≤ sqrt(S). Pentru primele 3 teste se observa ca cel putin o dimensiune este ≤ 10. Pentru celelalte teste avem:

  • 266 = 2 * 7 * 19
  • 539 = 7 * 7 * 11
  • 1630 = 2 * 5 * 163
  • 3495 = 3 * 5 * 233
  • 3653 = 13 * 281
  • 5866 = 2 * 7 * 419
  • 7294 = 2 * 7 * 521

Se observa ca in toate cazurile de mai sus, oricum am grupa numerele prime pentru a obtine dimensiunile matricii, cea mai mica dintre dimensiuni nu poate depasi 15. Deci, in toate testele, stim sigur ca min(M, N) ≤ 15. Sa presupunem ca aceasta dimensiune este numarul coloanelor, N, celalalt caz rezolvandu-se identic, rotind matricea.
Putem genera toate posibilitatile de a elimina exact C coloane din numarul total de N. Pentru fiecare caz generat, calculam suma elementelor ramase pentru fiecare linie in parte, si sortam aceste sume. Evident, vom elimina cele mai mici R sume.
Complexitatea unui astfel de algoritm este deci O(2N * (M log2 M + M*N)).

Triplete

(problema usoara, clasa a 10-a)

Pachete

(problema grea, clasa a 10-a)

1-sir

(problema usoara, clasele 11-12)

Diviz

(problema medie, clasele 11-12)

Problema se rezolva prin metoda programarii dinamice. Fie M[j][i]® numarul de moduri de a alege subsiruri distincte de lungime j din primele i cifre ale numarului N, subsiruri care sa dea restul r la impartirea K. Daca ne aflam in starea (j, i, r) putem sa actualizam starea (j+1, first[cif][i+1], (r*10+cif) mod K), considerand ca am adaugat la sfarsitul fiecarui subsir definit de (j, i, r) cifra cif. Prin first[cif][i] se defineste prima aparitie in numarul N a cifrei cif dupa pozitia i. Tabloul first va fi, evident, preprocesat. Pentru a numara subsirurile distincte ( adica sa nu numaram subsiruri egale de doua ori ), daca suntem in starea (j, i, r) actualizam starea (j+1, first[cif][i+1], (r*10+cif) mod K) daca si numai daca intre pozitiile i+1 si first[cif][i+1]-1 in numarul N nu mai apare nici o cifra cif. Acest lucru poate fi deasemenea calculat prin preprocesare, inainte de a incepe algoritmul de programare dinamica.
Complexitatea finala a algoritmului este O(K * L2), unde L este numarul de cifre ale numarului N.

Radiatie

(problema grea, clasele 11-12)

Sponsori

Organizarea finalei preONI este posibila datorita generosilor nostri sponsori: