Revizia anterioară Revizia următoare
 |    |
 Aceasta pagina nu este finalizata. Te rugam sa o imbunatatesti. |
Solutii Runda 2
Amlei
(problema usoara, clasa a 9-a, clasa a 10-a)
Primul pas al algoritmului este eliminarea conjunctiilor elementare care se repeta, deoarece A OR A = A. In continuare, se observa usor ca daca o conjunctie elementara apare doar intr-una din formule, distributia variabilelor care o face adevarata va conduce la rezultate diferite. Asadar, formulele sunt echivalente daca si numai daca contin aceleasi conjunctii elementare, facand abstractie de ordinea termenilor.
Problema se poate rezolva astfel sortand termenii fiecarei conjunctii si conjunctiile dupa un criteriu oarecare.
Tricouri
(problema medie, clasa a 9-a)
Zone
(problema grea, clasa a 9-a)
Pentru linia l1 si sumele corespunzatoarele zonelor 1, 2 si 4 o solutie potentiala ( adica un cvadruplu de forma l1, l2, c1, c2 ) este unic determinata deoarece elementele matricii initiale sunt pozitive. Astfel, vom determina intai coloana c1 pentru ca suma din regiunea 1 sa fie S1. Pentru c1 stabilit vom afla c2 astfel incat suma din regiunea 2 sa fie S2. Pentru a determina
Pentru a afla suma unei submatrici in O(1) se foloseste o matrice auxiliara de sume partiale: M[i][j] = suma elementelor din submatricea care are coltul stanga-sus in (1, 1) si coltul dreapta-jos in (i, j).
Plantatie
(problema medie, clasa a 10-a)
Culori
(problema grea, clasa a 10-a, problema medie, clasele 11-12)
Reguli
(problema usoara, clasele 11-12)
Ghiozdan
(problema grea, clasele 11-12)
Sponsori
Organizarea finalei preONI este posibila datorita generosilor nostri sponsori:
