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$
 
* talerul stang este mai greu - moneda falsa, in caz ca este mai grea, se va afla cu siguranta in multimea $A$ sau, in caz ca este mai usoara, se va afla in multimea $B$. Astfel, $H$ devine $H ∩ A$, iar $L$ devine $L ∩ B$
 
* talerul drept este mai greu - caz simetric cu cel anterior, $H$ devine $H ∩ B$, iar $L$ devine $L ∩ A$.
 
La final vom avea solutie daca si numai daca $|H| = 1 si |L| = 0$, caz in care moneda falsa este mai grea, sau $|H| = 0 si |L| = 1$, cand moneda falsa este mai usoara.
 
Complexitatea algoritmului care rezolva problema este $O(M*N)$
 

h2. 'Expresii 2':problema/expresii2
h3. (problema grea, clasa a 10-a)