Revizia anterioară Revizia următoare
 |    |
Solutii Runda 4
Next
(problema usoara, clasa a 9-a)
Folosind operatii pe numere mari se calculeaza restul lui N la numarul D. Fie R acest rest, se va aduna la numarul N valoarea (D-R) mod D (a mod b reprezinta restul numarului a la impartirea cu b). Numarul astfel obtinut va reprezenta primul numar mai mare sau egal decat N divizibil cu D. O prezentare detaliata a modului in care se pot implementa operatiile cu numere mari necesare se gaseste aici. Complexitatea rezolvarii este O(lg N).
Shop
(problema medie, clasa a 9-a)
La prima vedere, problema este asemanatoare cu problema rucsacului, deci se poate aborda folosind metoda programarii dinamice. Avand in vedere limita mare pentru numarul L o astfel de abordare nu ar fi obtinut punctaj maxim. Avand in vedere ca toate monezile sunt puteri ale numarului C, exista o rezolvare greedy: se determina cel mai mare tip de moneda CAi disponibil si se foloseste un numar maxim posibil de astfel de monede (minimul dintre L/CAi si Bi). Complexitatea unei astfel de solutii este O(logC L). O solutie care ar fi efectuat scaderi repetate ale cele mai mari monezi ar fi obtinut de asemenea punctaj maxim.
Dezastru
(problema grea, clasa a 9-a)
Bowling
(problema usoara, clasa a 10-a)
In primul rand, pentru a intelege solutia acestei probleme si altor probleme asemanatoare se recomanda citirea urmatoarelor documente despre teoria jocurilor:
- Teoria jocurilor: numerele Sprague-Grundy, GInfo Mai 2004, Cosmin Negruseri
- Game Theory Text: Impartial Combinatorial Games, Thomas Ferguson
Aceasta probleme se regaseste in literatura de specialitate si cu titlul de Kayles. Rezultatul pentru un joc se poate calcula in functie de XOR-ul numerelor Grundy pentru fiecare secventa de popice din sir. Cum N ≤ 50.000 trebuie calculate valorile Grundy pentru fiecare secventa de i popice cu i ≤ 50.000. Acestea se pot calcula in complexitate patratica si se pot pune in sursa ca un sir de constante. O alta solutie se foloseste de observatia ca incepand cu i = 72 sirul de valori se repeta cu perioada 12. Pentru fiecare test din fisier, complexitatea rezolvarii este O(N).
Regiuni
(problema medie, clasa a 10-a, problema usoara, clasele 11-12)
Elimin 2
(problema grea, clasa a 10-a)
Pentru a afla numarul maxim palindrom care este subsir al numarului N vom utiliza metoda programarii dinamice. Fie Li,j lungimea maxima a unui numar palindrom care se gaseste intre pozitiile i si j din numarul N. In momentul in care construim tabloul L consideram ca un numar poate incepe si cu cifra 0. Initial, Li,i = 1, pentru orice i de la 1 la numarul de cifre ale lui N. Vom calcula elementele tabloului L crescator in functie de marimea intervalelor (i,j). Daca consideram ca LEFTc,i este cea mai mica pozitie ≥ i in care apare cifra c in numarul N si RIGHTc,i cea mai mare pozitie ≤ i in care apare c in numarul N, avem urmatoarea relatie de recurenta:
Li,j = maxim(Li+1,j, Li,j-1, Li+1, RIGHT[N[i]][j]-1 + 2, LLEFT[N[j]][i]+1, j-1 + 2), unde prin Ni s-a notat a i-a cifra a numarului N. Relatia de recurenta trateaza urmatoarele cazuri:
- nu folosim cifra a i-a in solutia optima
- nu folosim cifra a j-a in solutia optima
- folosim cifra a i-a ( notata c ) in solutia optima. Pentru ca numarul intre i si j sa fie palindrom, este suficient sa aflam ultima pozitie p inainte de j a cifrei c, solutia optima intre i si j obtinandu-se din solutia optima intre i+1 si p-1 la care adaugam 2 cifre ( cele din capete ).
- folosim cifra a j-a ( notata c ) in solutia optima. Se trateaza similar.
Daca tablourile LEFT si RIGHT sunt construite inainte de a incepe programarea dinamica ( preprocesare ), putem construi tabloul L in complexitate O(NR_CIF2), unde NR_CIF este numarul de cifre ale lui N. Dupa ce am construit acest tablou, putem reconstitui solutia optima. Sa presupunem ca dorim sa cautam aceasta solutie intre pozitiile i si j si Li,j = X. Vom pune la capetele solutiei cea mai mare cifra c care indeplineste:
LLEFT[c,i]+1,RIGHT[c,j]-1 = X-2.
In final, eliminam 0-urile terminale ( de la ambele capete ale numarului palindrom ) si afisam acest numar. De precizat ca un algoritm de complexitate O(NR_CIF2) si constanta 10 ar fi obtinut in jur de 50 de puncte.
Distincte
(problema medie, clasele 11-12)
Laser
(problema grea, clasele 11-12)
Sponsori
Organizarea finalei preONI este posibila datorita generosilor nostri sponsori:
