h1. Solutii Happy Coding 2

Concursurile Happy Coding par sa fie singurele care nu au avut parte de descrieri ale solutiilor problemelor propuse.. Desi cu intarziere, intentionez sa remediez aceasta situatie. Aceasta pagina este "under construction" momentan.
 
 
 

Problemele date in cadrul acestui concurs au fost folosite pentru a selecta cele 3 echipe care au reprezentat Universitatea Politehnica Bucuresti la etapa regionala sud-est europeana a concursului ACM ICPC, in anul 2005.
h2. 'Expresii algebrice':problema/expresii

h2. 'Cercuri':problema/cercuri

O metoda simpla este translatam primul cerc in originea sistemului de axe de coordonate si sa il rotim pe cel de-al doilea pana cand centrul acestuia se afla pe axa $OX$ (la coordonata $X$ egala cu distanta dintre cele $2$ centre). Trebuie analizate cateva cazuri, pe baza valorilor razelor celor $2$ cercuri si a distantei dintre centrele lor. In cazul in care se decide ca cele $2$ cercuri se intersecteaza in $2$ puncte, vom observa ca, in urma translatiei si rotatie efectuate, cele $2$ puncte de intersectie se vor afla la aceeasi coordonata $x$, dar la coordonate $y$ opuse (egale in modul, dar opuse ca semn). VOm determina cele $2$ coordonate folosind teorema lui Pitagora generalizata in triunghiul format din centrele celor $2$ cercuri si fiecare din cele $2$ puncte de intersectie (deoarece cunoastem lungimile tuturor laturilor). Rezultatul pentru acest caz va fi apoi $2*|y|$.

O metoda simpla este translatam primul cerc in originea sistemului de axe de coordonate si sa il rotim pe cel de-al doilea pana cand centrul acestuia se afla pe axa $OX$ (la coordonata $X$ egala cu distanta dintre cele $2$ centre). Trebuie analizate cateva cazuri, pe baza valorilor razelor celor $2$ cercuri si a distantei dintre centrele lor. In cazul in care se decide ca cele $2$ cercuri se intersecteaza in $2$ puncte, vom observa ca, in urma translatiei si rotatie efectuate, cele $2$ puncte de intersectie se vor afla la aceeasi coordonata $x$, dar la coordonate $y$ opuse (egale in modul, dar opuse ca semn). Vom determina cele $2$ coordonate folosind teorema lui Pitagora generalizata in triunghiul format din centrele celor $2$ cercuri si fiecare din cele $2$ puncte de intersectie (deoarece cunoastem lungimile tuturor laturilor). Rezultatul pentru acest caz va fi apoi $2*|y|$.

h2. 'J-Arbore':problema/jarbore

Vom calcula $N[i]$, reprezentand cate noduri are arborele pe fiecare nivel (incepand de la $1$), precum si valoarea de pe prima muchie si de pe ultima muchie dintre nivelul $i-1$ si nivelul $i$ ({$v1[i] si v2[i]$}). Avem $N[1]=1$ si $v1[1]=v2[1]=0$. In cazul general, $N[i]=N[i-1]*(i-1)$, $v1[i]=v2[i-1]+1$ si $v2[i]=v1[i]+N[i]-1$. De asemenea, vom calcula cea mai mica si cea mai mare eticheta a unui nod de pe nivelul $i$: $vmin[i]=vmin[i-1]+v1[i]$ si $vmax[i]=vmax[i-1]+v2[i]$. Vom observa ca $24$ de nivele ale arborelui ajung pentru limitele date. Pentru fiecare numar $S$ dat vom gasi nivelul pe care s-ar afla (daca numarul exista in arbore), folosind valorile $vmin[i]$ si $vmax[i]$. Apoi, pentru a determina unde se afla numarul $S$, vom incerca sa deteminam pozitia acestuia in cadrul nivelului. Pentru aceasta vom realiza o cautare binara. Vom scrie o functie care va determina ce valoare se afla pe pozitia $p$ de pe nivelul $q$: aceasta valoare este valoare de pe pozitia $p/q$ de pe nivelul $q-1$, la care se adauga $v1[q]+p$ (considerand pozitiile numerotate de la $0$ in cadrul unui nivel). Vom determina astfel daca numarul $S$ exista si, daca da, vom reconstitui drumul de la el pana la radacina arborelui (ceea ce facem, oricum, in cadrul functiei de determinare a valorii de pe o pozitie $p$ de pe un nivel $q$).