h3. (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.
h2. Patrate3
h3. (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(N^2^ log N). Precizia recomandata este de 10^-4^.
h2. Elimin
h3. (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(2^N^ * (M log{~2~} M + M*N))$}.
h2. Triplete
h3. (problema usoara, clasa a 10-a)
