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 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.

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

h2. 'J-Arbore':problema/jarbore