h2. '1expr':problema/1expr

Problema se rezolva folosind programare dinamica. Pentru fiecare $K$ de la 1 la $3^8^$ se calculeaza lungimea minima a unei $1-expresii$ care are ca rezultat pe $K$, iar ultima operatie efectuata in cadrul acestei $1-expresii$ este $+$, $*$, $^$ sau $!$ (deci se calculeaza $4$ valori). Este important sa se calculeze toate aceste $4$ valori si nu doar o singura lungime minima a unei $1-expresii$ care il are ca rezultat pe $K$, deoarece este posibil ca acea $1-expresie$ sa se obtina folosind operatori de prioritate mica si, pentru a fi folosita in cadrul unor expresii mai mari, sa trebuiasca puse intre paranteze.
 
De exemplu, $1-expresia$ de lungimea minima pentru $8$ este: $1+1+(1+1+1)!$. O alta scriere a lui $8$, care are lungimea cu $1$ mai mare este: $(1+1)^(1+1+1)$. Insa aceasta a doua reprezentare a lui $8$ poate fi folosita fara a fi inclusa intre paranteze, daca trebuie inmultita cu o alta expresie, in timp ce prima scriere trebuie inclusa intre paranteze.
 
Programarea dinamica este implementata destul de usor (pentru un numar $K$):
 
* pentru $+$ : se incearca combinarea a doua expresii al caror rezultat este $X$, respectiv $K-X$
* pentru $*$ : combinarea a doua expresii al caror rezultat este $X$, respectiv $K/X$
* pentru $^$ : similar
* pentru $!$ : numai in cazul in care $K$ este factorialul unui numar (pentru limitele date, $K$ poate fi maxim $7!$ )
 
Se calculeaza la inceput cele $4$ valori pentru fiecare numar de la $1$ la limita maxima, apoi pentru fiecare numar dat in fisierul de intrare, doar se afisaza rezultatul (daca s-ar recalcula valorile pentru fiecare numar, s-ar depasi limita de timp).
 

h2. 'Cc':problema/cc
Problema cere determinarea unui cuplaj de cost minim, intr-un graf bipartit complet. Aceasta se poate realiza folosind un algoritm de flux maxim de cost minim sau, mai rapid, folosind algoritmul Ungar.

h2. 'Hprob':problema/hprob

Se vor numerota cele $4!=24$ de permutari posibile ale celor $4$ obiecte cu numere de la $1$ la $24$. Se va calcula apoi o matrice $A$, unde fiecare element $A[i][j]$ reprezinta probabilitatea ca daca un client gaseste obiectele in starea $j$, acesta sa le puna la loc in ordinea corespunzatoare starii $i$. Vom considera ca, initial, obiectele a aflau in ordinea corespunzatoare starii $1$ si vom calcula probabilitatea ca la sfarsit acestea sa se afle tot in starea $1$. Vom privi matricea $A$ calculata ca o matrice de iteratie. Vom avea un vector $V{~i~}[j]$ reprezentand probabilitatea ca obiectele sa se afle in starea $j$ dupa $k$ iteratii. Putem calcula pe $V{~i~}$ ca fiind $A*V{~i-1~}$. In felul acesta, $V{~N~}=A^N^*V{~0~}$. $V{~0~}$ are valoarea $1$ pe pozitia $1$ si $0$ pe celelalte pozitii, iar $A^N^$ poate fi calculata eficient folosind exponentiere logaritmica.

Se vor numerota cele $4!=24$ de permutari posibile ale celor $4$ obiecte cu numere de la $1$ la $24$. Se va calcula apoi o matrice $A$, unde fiecare element $A[i][j]$ reprezinta probabilitatea ca daca un client gaseste obiectele in starea $j$, acesta sa le puna la loc in ordinea corespunzatoare starii $i$. Vom considera ca, initial, obiectele se aflau in ordinea corespunzatoare starii $1$ si vom calcula probabilitatea ca la sfarsit acestea sa se afle tot in starea $1$. Vom privi matricea $A$ calculata ca o matrice de iteratie. Vom avea un vector $V{~i~}[j]$ reprezentand probabilitatea ca obiectele sa se afle in starea $j$ dupa $k$ iteratii. Putem calcula pe $V{~i~}$ ca fiind $A*V{~i-1~}$. In felul acesta, $V{~N~}=A^N^*V{~0~}$. $V{~0~}$ are valoarea $1$ pe pozitia $1$ si $0$ pe celelalte pozitii, iar $A^N^$ poate fi calculata eficient folosind exponentiere logaritmica.

h2. 'Nodiv':problema/nodiv
h2. 'Arbore de cicluri':problema/arbciclu

Vom realiza urmatoarea operatie in mod repetat, pana cand operatia nu mai poate fi aplicata: daca exista un nod $i$ avand gradul $2$, iar vecinii acestuia sunt $j$ si $k$, eliminam nodul $i$ din graf si introducem muchia $j-k$, daca aceasta muchie nu exista deja. Daca graful dat este un arbore de cicluri, atunci la final trebuie sa ramanem cu doar $2$ noduri (si, initial, numarul de noduri trebuie sa fi fost cel putin $3$). Pentru a aplica operatia descrisa in mod eficient, vom folosi o coada in care vom introduce nodurile cu gradul $2$. De fiecare data cand extragem din coada un nod $i$, exista posibilitatea sa modificam gradele vecinilor acestuia, $j$ si $k$; daca $j$ sau $k$ ajunge sa aiba gradul $2$ in urma eliminarii lui $i$, il introducem si pe el in coada. Mai trebuie sa folosim o structura de date eficienta pentru a determina rapid daca $2$ noduri sunt adiacente, precum si pentru a elimina noduri din "lista" de adiacenta a altor noduri (in implementarea solutiei oficiale s-au folosit arbori echilibrati, prin intermediul structurii "set" din STL).

Vom realiza urmatoarea operatie in mod repetat, pana cand operatia nu mai poate fi aplicata: daca exista un nod $i$ avand gradul $2$, iar vecinii acestuia sunt $j$ si $k$, eliminam nodul $i$ din graf si introducem muchia $j-k$, daca aceasta muchie nu exista deja. Daca graful dat este un arbore de cicluri, atunci la final trebuie sa ramanem cu doar $2$ noduri (si, initial, numarul de noduri trebuie sa fi fost cel putin $3$). Pentru a aplica operatia descrisa in mod eficient, vom folosi o coada in care vom introduce nodurile cu gradul $2$. De fiecare data cand extragem din coada un nod $i$, exista posibilitatea sa modificam gradele vecinilor acestuia, $j$ si $k$; daca $j$ sau $k$ ajung sa aiba gradul $2$ in urma eliminarii lui $i$, ii introducem si pe ei in coada. Mai trebuie sa folosim o structura de date eficienta pentru a determina rapid daca $2$ noduri sunt adiacente, precum si pentru a elimina noduri din "lista" de adiacenta a altor noduri (in implementarea solutiei oficiale s-au folosit arbori echilibrati, prin intermediul structurii "set" din STL).

h2. 'Gandaci Java':problema/java