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

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

Aceasta problema este cunoscuta si ca 'Teorema chineza a restului':http://en.wikipedia.org/wiki/Chinese_remainder_theorem .
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.
 

h2. 'Cercuri':problema/cercuri
h2. 'J-Arbore':problema/jarbore