h2. 'Palindroame':problema/palind

Pentru a avea solutie este necesar ca cel mult un singur caracter sa apara in sir de un numar impar de ori. In mod evident, nu vom inversa niciodata o pereche de caractere alaturate identice. Din acest motiv, in cadrul palindromului pe care il vom obtine, prima aparitie a unui caracter va fi "imperecheata" cu ultima aparitie a acelui caracter, a doua aparitie cu penultima s.a.m.d. In felul acesta, fiecare pereche defineste un interval $(a,b)$, $a$ reprezentand pozitia caracterului din stanga din cadrul perechii, iar $b$ reprezentand pozitia caracterului din dreapta din cadrul perechii. Singura conditie pentru ca numarul de inversiuni sa fie minim este sa nu ajungem sa inversam niciodata intre ele capetele a $2$ intervale care sunt incluse unul intr-altul. Pornind de la aceasta observatie, putem alege mereu intervalul corespunzator primului element al sirului si sa ducem pe ultima pozitie a sirului capatul dreapta al acestui interval, ramanand apoi cu un sir mai mic. In cazul in care primul element al sirului este caracterul ce trebuie sa se afle in mijlocul palindromului (pentru numar impar de caractere), atunci vom alege intervalul ce corespunde ultimei pozitii a sirului. Vom repeta acest procedeu pana cand ramanem cu un sir de lungime $0$ sau $1$.

Pentru a avea solutie este necesar ca maxim un singur caracter sa apara in sir de un numar impar de ori. In mod evident, nu vom inversa niciodata o pereche de caractere alaturate identice. Din acest motiv, in cadrul palindromului pe care il vom obtine, prima aparitie a unui caracter va fi "imperecheata" cu ultima aparitie a acelui caracter, a doua aparitie cu penultima s.a.m.d. In felul acesta, fiecare pereche defineste un interval $(a,b)$, $a$ reprezentand pozitia caracterului din stanga din cadrul perechii, iar $b$ reprezentand pozitia caracterului din dreapta din cadrul perechii. Singura conditie pentru ca numarul de inversiuni sa fie minim este sa nu ajungem sa inversam niciodata intre ele capetele a $2$ intervale care sunt incluse unul intr-altul. Pornind de la aceasta observatie, putem alege mereu intervalul corespunzator primului element al sirului si sa ducem pe ultima pozitie a sirului capatul dreapta al acestui interval, ramanand apoi cu un sir mai mic. In cazul in care primul element al sirului este caracterul ce trebuie sa se afle in mijlocul palindromului (pentru numar impar de caractere), atunci vom alege intervalul ce corespunde ultimei pozitii a sirului. Vom repeta acest procedeu pana cand ramanem cu un sir de lungime $0$ sau $1$.

h2. 'Lungimi de interval':problema/linterv

* capatul stanga al intervalului curent este mai mic decat $X$, iar capatul dreapta al acestuia este mai mic sau egal cu $X$ => nu realizam nici o actiune si mergem mai departe
* capatul stanga al intervalului curent este mai mic decat $X$, iar capatul dreapta al acestuia este mai mare decat $X$ => adunam la $L$ diferenta dintre capatul dreapta al intervalului curent si $X$, iar apoi setam pe $X$ la valoarea capatului dreapta al intervalului curent.

Complexitatea solutiei este $O(N*logN + N)=O(N*logN)$.
 

h2. 'Resturi':problema/resturi
Vom calcula numarul cerut in mod incremental. La pasul $i$ vom avea calculat numarul $Q$, reprezentand cel mai mic numar care respecta primele $i$ relatii (deci $Q mod p{~j~}=r{~j~}$ pentru orice $j ≤ i$). La pasul $1$, $Q$ este egal chiar cu $r{~1~}$. Avand calculat numarul $Q$ la pasul $i$, va trebui sa determinam numarul $Q'$ la pasul $i+1$ care respecta primele $i+1$ relatii. Acest numar $Q'$ este de forma $Q + x*M$, cu $x ≥ 0$, unde $M$ este cel mai mic multiplu comun al numerelor $p{~1~},...,p{~i~}$ (fiind numere prime, $M$ este chiar produsul lor). Ideea din spatele acestei formule este ca la numarul $Q$ trebuie adunat un multiplu al numarului $M$, pentru ca numarul obtinut $Q'$ sa pastreze aceleasi resturi la impartirile la primele $i$ numere prime date. Avem acum urmatoarea ecuatie: $Q + x*M = r{~i+1~} (mod p{~i+1~})$. Trecand pe $Q$ in partea dreapta, obtinem o ecuatie de forma $A*x = B (mod P)$, care se poate rezolva direct, folosind algoritmul lui Euclid extins, pentru a calcula inversul multiplicativ al lui $A$, relativ la numarul prim $P$. O metoda mai simpla de rezolvare a ecuatiei se bazeaza pe a incerca toate valorile posibile pentru $x$, intre 0 si $p{~i+1~}-1$, care functioneaza deoarece valorile numerelor prime sunt relativ mici (mai mici decat $1000$).

h2. 'Curse de cai':problema/cai

Vom sorta caii lui Gigel si Ionel in ordine descrescatoare si ii vom renumerota conform acestei ordini. Vom considera ca Gigel decide pentru fiecare cal al lui Ionel, in ordinea sortata, ce cal de-al sau sa ii opuna in cursa. Solutia prezentata in continuare se bazeaza pe urmatoarea observatie. Sa presupunem ca Gigel a decis ce cai de-ai sai vor concursa impotriva primilor $i$ cai ai lui Ionel si urmeaza sa decida pentru al $i+1-lea$ cal. Singurele doua variante fezabile pe care le are Gigel este sa aleaga cel mai bun cal al sau (dintre cei ramasi) si sa il puna sa concureze cu al $i+1$-lea cal al lui Ionel sau sa aleaga cel mai prost cal al sau. Vom calcula o matrice $C[i][j]$ reprezentand costul maxim pe care il poate obtine Gigel daca i-au mai ramas caii de la $i$ la $j$ (asta inseamna ca toti caii de la $1$ la $i-1$ au fost deja selectati si la fel si toti caii de la $j+1$ la $N$; de aici rezulta ca Gigel a ales dja adevrsai pentru primii $N-j+i-1$ cai de-ai lui Ionel si acum trebuie sa aleaga adversar pentru urmatorul cal al lui Ionel). $C[i][j]$ se calculeaza pe baza lui $C[i+1][j]$ (daca Gigel alege cel mai bun cal al sau impotriva calului curent al lui Ionel) sau pe baza lui $C[i][j-1]$ (daca elege cel mai prost cal al sau), alegandu-se varianta de cost maxim.

Vom sorta caii lui Gigel si Ionel in ordine descrescatoare si ii vom renumerota conform acestei ordini. Vom considera ca Gigel decide pentru fiecare cal al lui Ionel, in ordinea sortata, ce cal de-al sau sa ii opuna in cursa. Solutia prezentata in continuare se bazeaza pe urmatoarea observatie. Sa presupunem ca Gigel a decis ce cai de-ai sai vor concursa impotriva primilor $i$ cai ai lui Ionel si urmeaza sa decida pentru al $i+1-lea$ cal. Singurele doua variante fezabile pe care le are Gigel este sa aleaga cel mai bun cal al sau (dintre cei ramasi) si sa il puna sa concureze cu al $i+1$-lea cal al lui Ionel sau sa aleaga cel mai prost cal al sau. Vom calcula o matrice $C[i][j]$ reprezentand costul maxim pe care il poate obtine Gigel daca i-au mai ramas caii de la $i$ la $j$ (asta inseamna ca toti caii de la $1$ la $i-1$ au fost deja selectati si la fel si toti caii de la $j+1$ la $N$; de aici rezulta ca Gigel a ales deja adversari pentru primii $N-j+i-1$ cai de-ai lui Ionel si acum trebuie sa aleaga adversar pentru urmatorul cal al lui Ionel). $C[i][j]$ se calculeaza pe baza lui $C[i+1][j]$ (daca Gigel alege cel mai bun cal al sau impotriva calului curent al lui Ionel) sau pe baza lui $C[i][j-1]$ (daca elege cel mai prost cal al sau), alegandu-se varianta de cost maxim.

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 sa 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$).

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]$ (cautam acel nivel $i$ pentru care $vmin[i] ≤ S ≤ 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$).