Solutii FMI No Stress 2012
(toc)*{text-align:center} Lista de probleme
* Cercuri4
* Parantezare
* Tamplar
* Invazie
* Vmin
* Potrivire
* Costperm
* Berarii2
* Fpwl

Cercuri4

Solutie O(N² + NlogN)

Se sorteaza cercurile descrescator dupa raza, deoarece un cerc cu o raza R nu poate fi inclus decat intr-un cerc cu o raza R1 >= R.Dupa sortare toate cercurile ce pot include cercul i se vor gasi inaintea acestuia.
Astfel putem aplica un algoritm asemanator celui de cel mai lung subsir crescator pentru a obtine frumusetea maxima, relatia de recurenta obtinuta fiind :
Fmax[ i ] = Frumusete[ i ] + max(Fmax[ j ] | j < i si cercul j include cercul i).
Pentru a verifica incluziunea a 2 cercuri (C1,R1) respectiv (C2, R2) urmatoarea relatie trebuie satisfacuta : distanta (C1,C2) + min(R1,R2) <= max(R1,R2). unde C reprezinta centrul cercului iar R raza .

Parantezare

Solutie O(M + LungimeaExpresiei)

Solutia foloseste o stiva St si un vector Poz ( acest vector retine pozitia parantezei ')' corespunzatoare parantezei '(' de pe pozitia i ).
Se parcurge sirul de intrare caracter cu caracter, pentru fiecare caracter verificandu-se tipul acestuia.
Daca sir[ i ] = '(' , atunci se adauga in stiva pozitia i
Daca sir[ i ] = ')' , se actualizeaza Poz[St[Varf]], deoarece paranteza ')' este paranteza ce corespunde celei de pe pozitia St[Varf].
Caractere care nu sunt paranteze se ignora .

Tamplar

Complexitate O(L) * nr_mari

Solutia problemei o reprezinta numarul (L - 1)!. Pentru calcularea acestui numar sunt necesare operatiile pe numere mari.

Invazie

Vmin