Notam $A{~i~}$ multimea perechilor al caror produs se scrie sub forma {$x^i^$} cu {$x$} numar natural. Problema ne cere calcularea cardinalului reuniunii multimilor $A{~i~}$.

In continuare vom arata un mod de a calcula cardinalul unei multimi multimi {$A{~i~}$}. Se observa ca o pereche (a,b,c) (x,y,z) apartine multimii {$A{~i~}$} daca {$a+x=0$},{$b+y=0$} si {$c+z=0$} (mod {$i$}). Vom constui un tablou {$Nr[r1][r2][r3]$} care reprezinta numarul de triplete (x,y,z) cu proprietatea {$r1=x$},{$r2=y$},{$r3=z$} (mod {$i$}). Vom adauga la cardinalul multimii {$A{~i~}$} produse de forma {$Nr[a][b][{@c@}]*Nr[i-a][i-b][i-c]$} ({$i-a,i-b,i-c$} se calculeaza tot mod {$i$}). Deasemenea trebuie avut grija la numerele pentru care {$2*a=0$} {$2*b=0$} si {$2*c=0$} (mod {$i$}), deoarece trebuie adunat $Nr[a][b][{@c@}]*(Nr[a][b][{@c@}]-1)/2$ pentru a nu numara aceeasi pereche de mai multe ori.

In continuare vom arata un mod de a calcula cardinalul unei multimi multimi {$A{~i~}$}. Se observa ca o pereche $(a,b,c) (x,y,z)$ apartine multimii {$A{~i~}$} daca {$a+x=0$},{$b+y=0$} si {$c+z=0$} (mod {$i$}). Vom constui un tablou {$Nr[r1][r2][r3]$} care reprezinta numarul de triplete $(x,y,z)$ cu proprietatea {$r1=x$},{$r2=y$},{$r3=z$} (mod {$i$}). Vom adauga la cardinalul multimii {$A{~i~}$} produse de forma {$Nr[a][b][{@c@}]*Nr[i-a][i-b][i-c]$} ({$i-a,i-b,i-c$} se calculeaza tot mod {$i$}). Deasemenea trebuie avut grija la numerele pentru care {$2*a=0$} {$2*b=0$} si {$2*c=0$} (mod {$i$}), deoarece trebuie adunat $Nr[a][b][{@c@}]*(Nr[a][b][{@c@}]-1)/2$ pentru a nu numara aceeasi pereche de mai multe ori.

O observatie care ne va ajuta sa calculam cardinalul reununiunii este faptul ca daca un numar se scrie de forma $x^i*j^$ el se poate scrie si sub forma {$y^i^$}, unde $y$ va fi chiar $x^j^$. Asadar $A{~i*j~}$ este inclusa in {$A{~i~}$}. Deci ne va interesa reuniunea multimilor {$A{~i~}$} pentru $i$ produs de numere prime. Cardinalul acestei reuniunii se va calcula folosind principiul includerii si excluderii:

h3. (problema usoara, clasa a 10-a)

Problema se rezolva mentinand doua multimi $H$ si $L$ continand monedele candidate pentru moneda mai grea, respectiv cele candidate pentru moneda mai usoara. Initial $H$ si $L$ contin fiecare toate elementele multimii @{1..N}@. Cele doua multimi se vor actualiza dupa fiecare cantarire. Notand cu $A$ multimea monedelor asezate pe bratul stang si cu $B$ multimea monedelor asezate pe bratul drept al balantei, vom proceda in felul urmator:
* talerele sunt echilibrate - este clar ca nici una din monedele din $A$ sau $B$ nu poate fi mai grea/mai usoara, deci $H$ va deveni $H - A - B$, iar $L$ va deveni $L - A - B$

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

Problema se rezolva folosind programarea dinamica. Mai intai calculam o matrice $V$, unde $V[i, j]$ reprezinta numarul de sfarsituri valabile de expresii ce se pot forma ce necesita adaugarea a j variabile la inceput pentru a se forma o expresie corecta. Relatiile de recurenta se determina usor urmarind cu atentie in ce configuratii putem ajunge din configuratia actuala (putem pune o variabila, $+$, $*$ sau $!$).

Problema se rezolva folosind programarea dinamica. Mai intai calculam o matrice $V$, unde $V[i, j]$ reprezinta numarul de sfarsituri valabile de expresii ce se pot forma ce necesita adaugarea a $j$ variabile la inceput pentru a se forma o expresie corecta de lungime $i$. Relatiile de recurenta se determina usor urmarind cu atentie in ce configuratii putem ajunge din configuratia actuala (putem pune o variabila, $+$, $*$ sau $!$).

Rezolvarea celei de-a 2-a parti a problemei implica folosirea matricei $V$. Avand valorile calculate putem afla caracterul pe care trebuie sa il punem pe o anumita pozitie. Este evident ca la fiecare pas indicele expresiei cautate scade cu numarul de expresii peste care "sarim".
h2. 'Ograzi':problema/ograzi