Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-02-18 21:33:27.
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)

Dupa ce citim cele N numere din fisierul de intrare, vom realiza o preprocesare (filtrare) in urmatorul mod:
Mi, j va fi o lista ( implementata fie ca vector, fie ca lista liniara simplu inlantuita ) care va retine in ordine descrescatoare numerele din fisierul de intrare care dau restul j la impartirea cu i. Deoarece pentru fiecare interogare numarul de termeni este cel mult 5, este suficient ca aceasta lista sa retina cel mult 5 termeni. Astfel, in momentul in care citim un element de valoare x, pentru fiecare i de la 2 la 20, vom introduce elementul in lista Mi, x mod i daca si numai daca aceasta lista nu contine inca 5 termeni sau x este mai mare decat minimul din lista ( in acest ultim caz x va fi copiat peste acest minim, asigurand ca in lista vor ramane cele mai mari numere posibile ).
In momentul in care citim o interogare de forma K P, vom genera toate posibilitatile de resturi la impartirea cu P ale primelor K-1 numere din suma, al K-lea rest fiind unic determinat. Pentru o astfel de configuratie de resturi stim in timp O(1) care este cea mai mare suma ( daca exista ) a unor elemente care sa aiba resturile astfel stabilite, prin utilizarea informatiilor din tabloul M.
De exemplu, daca K = 3 si P = 4, pentru primele doua resturi stabilite ale primelor doua numere ( sa zicem ca aceste resturi au valoarea 3 si respectiv 2), restul celui de-al treilea numar la impartirea cu 4 nu poate fi decat 3. Acum, folosind tabloul M calculat anterior, trebuie sa stim care sunt cele mai mari doua numere care dau la impartirea cu 4 restul 3 si care este cel mai mare numar care la impartirea cu 4 da restul 2. Aceasta suma poate fi calculata deci in O(1). Vom genera ( prin metoda backtracking sau folosind mai multe for-uri imbricate ) toate configuratiile posibile de resturi, si o vom retine pe cea care genereaza suma cea mai mare, suma pe care ulterior o vom afisa. Complexitatea finala este deci O(N + M * PK-1), care asigura punctajul maxim, folosind nivelul cunostintelor de clasa a IX-a.

O alta solutie mai eleganta dar care depaseste cunostintele de clasa a IX-a ar fi cea care foloseste programarea dinamica in modul urmator: se noteaza cu Di,j,r care este suma maxima folosind i numere din primele j resturi posibile la impartirea cu P si pana in momentul curent sa avem format restul r. Se construieste acest tablou in mod bttom-up. Raspunsul se va afla in DK,P-1,0. Complexitatea unui astfel de algoritm este O(N + M * K2 * P2), care de asemenea obtine 100 de puncte.

Zone

(problema grea, clasa a 9-a)

Se observa ca daca stim linia L1 si suma asociata zonei 1, coloana C1 este unic determinata deoarece elementele matricii initiale erau pozitive: pornind cu submatricea de colturi (1, 1) si (L, 1), va trebui sa crestem C1 pana cand suma submatricii de colturi (1, 1) si (L1, C1) va deveni cat am stabilit initial. Cum suma submatricii de colturi (1, 1) si (L1, X) este mai mica decat suma submatricii de colturi (1, 1) si (L1, X+1), cautarea coloanei C1 poate fi realizata prin cautare binara. Dupa ce am determinat C1, stabilim care dintre cele 8 sume ramase este valoarea zonei 2 si determinam in mod similar valoarea coloanei C2. Apoi stabilim care dintre cele 7 sume ramase este valoarea pe care o vom asocia zonei 4 si determinam si L2. Pentru un cvadruplu astfel determinat, L1, C1, L2 si C2, vom determina toate cele 9 sume care se formeaza si daca ele sunt egale cu sumele impuse initial, atunci inseamna ca avem o solutie. Dintre toate solutiile posibile o vom afisa in final pe cea care respecta conditiile de minimalitate enuntate.

In momentul in care cautam binar o linie sau o coloana va trebui sa aflam suma pentru o anumita submatrice. Pentru a realiza acest lucru eficient, vom construi de la inceput matricea de sume partiale S, unde Si,j reprezinta suma elementelor din submatricea care are coltul stanga-sus in (1, 1) si coltul dreapta-jos in (i, j). Astfel, suma submatricii de colturi (x1, y1)-(x2, y2) va fi egala cu Sx2,y2 - Sx1-1,y2 - Sx2,y1-1 + Sx1-1,y1-1.

Problema este astfel rezolvata in intregime. Complexitatea algoritmului este O(N2).

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: