Revizia anterioară Revizia următoare
 |    |
Solutii Runda 4
Next
(problema usoara, clasa a 9-a)
Shop
(problema medie, clasa a 9-a)
Dezastru
(problema grea, clasa a 9-a)
Bowling
(problema usoara, clasa a 10-a)
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:
