h3. (problema grea, clasa a 9-a)

Daca o problema de probabilitati ar fi putut incurca o parte a concurentilor de clasa a 9-a, exemplele date in enunt reprezinta un indiciu destul de clar in legatura cu modalitatea de rezolvare. Din moment ce evenimentele pot aparea in orice ordine, avem $N!$ posibilitati. Ar trebui, deci, sa generam toate permutarile, sa calculam pentru fiecare permutare produsul primelor $K$ valori, si sa facem media aritmetica a rezultatelor obtinute. Problema se reduce succesiv la aranjamente si apoi la combinari, fiind suficient sa consideram toate modurile de a alege $K$ evenimente, indiferent de ordine. Solutiile cu permutari si aranjamente obtin punctaje partiale, in functie de grija acordata implementarii.
 
Problema se poate rezolva si folosind programarea dinamica. Se construieste matricea $A{~i,j~}$ cu semnificatia suma tuturor produselor de $j$ factori alesi din primele $i$ numere. Recurenta se poate calcula usor {$A{~i,j~}=A{~i-1,j~}+A{~i-1,j-1~}*P{~i~}$}. Probabilitatea ceruta va fi $A{~n,k~}$ impartita la $C{~n,k~}$ (combinari de $n$ luate cate {$k$}). Complexitate $O(n*k)$.
 

h2. 'Bowling':problema/bowling
h3. (problema usoara, clasa a 10-a)

* 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_CIF^2^)$}, 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 {$L{~i,j~}$} = {$X$}. Vom pune la capetele solutiei cea mai mare cifra $c$ care indeplineste:
{$L{~LEFT[c,i]+1,RIGHT{@[c,j]@}-1~}$} = {$X-2$}.

Daca tablourile $LEFT$ si $RIGHT$ sunt construite inainte de a incepe programarea dinamica ( preprocesare ), putem construi tabloul $L$ in complexitate {$O(NR_CIF^2^)$}, unde $NR_CIF$ este numarul de cifre ale lui {$N$}. Dupa ce am construit acest tablou, putem reconstitui solutia optima. Sa presupunem ca solutia optima incepe cu cifra nenula {$c$}. Fie $x$ prima aparitie a cifrei $c$ in numarul $N$, si $y$ ultima aparitie. Vom selecta acea cifra $c$ pentru care valoarea {$L{~x,y~}$} este maxima. Pentru valori egale se alege cifra maxima. Dupa ce am determinat valoarea primei cifre, putem presupune ca dorim sa cautam solutia optima intre pozitiile {$i$} si {$j$} si {$L{~i,j~}$} = {$X$}. Vom pune la capetele solutiei cea mai mare cifra $c$ care indeplineste: {$L{~LEFT[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_CIF^2^)$} si constanta $10$ ar fi obtinut in jur de 50 de puncte.

De precizat ca un algoritm de complexitate {$O(NR_CIF^2^)$} si constanta $10$ ar fi obtinut in jur de 50 de puncte.

h2. 'Distincte':problema/distincte