==include(page="preoni-2008/runda-1/solutii/ordine")==

h2(#multimi2). 'Multimi 2':problema/multimi2

==include(page="preoni-2008/runda-1/solutii/multimi2")==

h2(#ecuatie). 'Ecuatie':problema/ecuatie

==include(page="preoni-2008/runda-1/solutii/ecuatie")==

h2(#economie). 'Economie':problema/economie

==include(page="preoni-2008/runda-1/solutii/economie")==

h2(#teren). 'Teren':problema/teren

==include(page="preoni-2008/runda-1/solutii/teren")==

h2(#pairs). 'Pairs':problema/pairs

==include(page="preoni-2008/runda-1/solutii/pairs")==

Problema admite o rezolvare triviala de complexitate {$O(N^2^log MAX)$}, unde $MAX$ este maximul dintre cele $N$ numere ale multimii {$M$}: pentru fiecare pereche de numere din multimea data se calculeaza cel mai mare divizor comun folosind algoritmul lui Euclid. O astfel de rezolvare obtine 20-30 de puncte, in functie de prezenta unor optimizari. Rezolvarea optima are complexitatea {$O(MAX log MAX)$} si se baza pe faptul ca {$O(N/1 + N/2 + N/3 ... + N/N)$} = {$O(N log N)$}, pentru orice {$N$}.
Din numarul total de perechi, {$N*(N-1)/2$}, vom scadea numarul de perechi {$(x y)$}, astfel incat $x$ si $y$ nu sunt prime intre ele si vom obtine rezultatul cerut. Notam cu $Res$ numarul de perechi {$(x y)$}, cu {$cmmdc(x, y) > 1$}. Pentru a afla efectiv numarul $Res$ vom folosi procedeul includerii si excluderii. Fie {$x{~i~}$} numarul de numere din $M$ care se divid cu {$i$}. Vectorul $x$ se poate calcula in {$O(MAX log MAX)$}: pentru fiecare numar $i$ de la $1$ la $MAX$ verificam cate din numerele {$i$}, {$2i$}, {$3i$} ... {$[MAX/i]*i$} apartin multimii {$M$}. Consideram toate numerele $P$ ce se scriu ca produs de numere prime, unde fiecare numar prim este folosit cel mult o data. Daca numarul de numere prime din descompunerea lui $P$ este un numar impar, adunam {$x{~P~}$} la {$Res$}. Altfel, din {$Res$} scadem {$x{~P~}$}.
Rezolvarea de complexitate {$O(MAX log MAX)$} asigura obtinerea punctajului maxim.

==include(page="preoni-2008/runda-1/solutii/aliens")==

h2(#aliens). 'Aliens':problema/aliens

==include(page="preoni-2008/runda-1/solutii/tunel")==

Problema se rezolva cu ajutorul programarii dinamice. Fiecare fractie din cele date se poate scrie ca un produs de forma {$2^x^ * 3^y^ * 5^z^$}, unde {$x$}, $y$ si $z$ sunt numere intregi. Daca codificam fiecare fractie prin tripletul corespunzator, problema revine la a selecta anumite triplete {$(x{~1~}, y{~1~}, z{~1~})$}, {$(x{~2~}, y{~2~}, z{~2~})$}... {$(x{~K~} y{~K~} z{~K~})$} din cele $N$ astfel incat:
 
* {$x{~1~} + x{~2~} + ... + x{~K~} ≥ 0$}
* {$y{~1~} + y{~2~} + ... + y{~K~} ≥ 0$}
* {$z{~1~} + z{~2~} + ... + z{~K~} ≥ 0$}
* 2^(x{~1~} + x{~2~} + ... + x{~K~})^ * 3^(y{~1~} + y{~2~} + ... + y{~K~})^ * 5^(z{~1~} + z{~2~} + ... + z{~K~})^ sa fie maxim posibil.
 
Problema se rezolva prin programare dinamica. Fie {$D{~i, x3, x5~}$} valoarea maxim posibila pentru exponentul lui $2$ care se poate obtine din primele $i$ fractii, astfel incat exponentul lui $3$ sa fie $x3$ si exponentul lui $5$ sa fie {$x5$}. Tabloul {$D$} poate contine si indici negativi! Relatia de recurenta este urmatoarea:
{$D{~i, x3, x5~}$} = maxim({$D{~i-1, x3, x5~}, x2' + D{~i-1, x3-x3', x5-x5'~}$}), unde {$(x2' x3' x5')$} este tripletul asociat celei de a {$i$}-a fractii.
Din considerente de memorie nu vom retine tot tabloul {$D$}. Deoarece elementele de pe pozitii de forma ({$i, a, b$}) depind doar de elemente de pe pozitii de forma ({$i-1, a', b'$}) vom retine o singura matrice in locul unui tablou tridimensional si vom actualiza elementele din aceasta matrice printr-o parcurgere convenabila a indicilor.
Dupa ce avem tabloul $D$ construit, aflam maxim({$2^D{~N,x3,x5~}^ * 3^x3^ * 5^x5^$}), cu {$D{~N, x3, x5~} ≥ 0$}, $x3 ≥ 0$ si {$x5 ≥ 0$}. Pentru a compara doua numere $2^x1^ * 3^y1^ * 5^z1^$ si $2^x2^ * 3^y2^ * 5^z2^$ vom logaritma si vom compara {$x1*ln2 + y1*ln3 + z1*ln5$} cu {$x2*ln2 + y2*ln3 + z2*ln5$}. Atunci cand am aflat o solutie optima, este necesara implementarea operatiilor pe numere mari, deoarece rezultatul nu se incadreaza in nici un tip de date conventional.
Complexitatea problemei este {$O(N^3^)$} de constanta {$4*(log{~3~}MAX)*(log{~5~}MAX)$}, unde {$MAX = 400.000.000$}. Aceasta solutie obtine 100 de puncte.
 
h2(#tunel). 'Tunelul groazei':problema/tunel
 
h2(#nkperm). 'NKPerm':problema/nkperm

==include(page="preoni-2008/runda-1/solutii/nkperm")==