h1. Solutii Happy Coding 1

Problemele date in cadrul acestui concurs au fost folosite initial la preselectia individuala a studentilor ce au alcatuit echipele ce au reprezentat Universitatea Politehnica Bucuresti la concursul ACM ICPC, in anul 2005.

Problemele date in cadrul acestui concurs au fost folosite initial la preselectia individuala a studentilor ce au alcatuit echipele care au reprezentat Universitatea Politehnica Bucuresti la concursul ACM ICPC, in anul 2005.

h2. 'Arie':problema/arie

O metoda simpla consta in deteerminarea punctelor de intersectie intre orice latura a primului poligon si orice latura a celui de-al doilea. Apoi se determina varfurile primului poligon aflate in interiorul celui de-al doilea poligon, precum si varfurile celui de-al doilea poligon aflate in interiorul primului poligon. Se realizeaza apoi o infasuratoare convexa a punctelor astfel determinate. Ca varianta mai simpla, intrucat stim sigur ca punctele determinate sunt varfurile unui poligon convex ce reprezinta aria intersectiei celor $2$ poligoane date, putem calcula un punct "central", reprezentat de media aritmetica a coordonatelor punctelor determinate. Apoi vom sorta punctele in jurul acestui punct "central", determinand astfel ordinea acestora pe conturul poligonului intersectie. Se calculeaza apoi aria poligonului intersectie, folosind formula bine cunoscuta bazata pe suma determinantilor $2x2$, cate unul pentru fiecare latura a poligonului intersectie, ce contin coordonatele celor $2$ puncte ale fiecarei laturi.

O metoda simpla consta in determinarea punctelor de intersectie intre orice latura a primului poligon si orice latura a celui de-al doilea. Apoi se determina varfurile primului poligon aflate in interiorul celui de-al doilea poligon, precum si varfurile celui de-al doilea poligon aflate in interiorul primului poligon. Se realizeaza apoi o infasuratoare convexa a punctelor astfel determinate. Ca varianta mai simpla, intrucat stim sigur ca punctele determinate sunt varfurile unui poligon convex ce reprezinta aria intersectiei celor $2$ poligoane date, putem calcula un punct "central", reprezentat de media aritmetica a coordonatelor punctelor determinate. Apoi vom sorta punctele in jurul acestui punct "central", determinand astfel ordinea acestora pe conturul poligonului intersectie. Se calculeaza apoi aria poligonului intersectie, folosind formula bine cunoscuta bazata pe suma determinantilor $2x2$, cate unul pentru fiecare latura a poligonului intersectie, ce contin coordonatele celor $2$ puncte ale fiecarei laturi.

h2. 'Bile':problema/bile

h2. 'Suma':problema/suma

Suma data se poate ca scrie ca <tex> \displaystyle\sum_{i = 1}^N i^2 </tex> - <tex> \displaystyle\sum_{i = 1}^N i </tex>. Prima suma este egala cu $N*(N+1)*(2*N+1)/6$. A doua suma este egala cu $N*(N+1)/2$. Se vor calcula restul impartirii primei sume la $P$ ({$R{~1~}$}) si restul impartitii celei de-a doua sume la $P$ ({$R{~2~}$}). Pentru aceasta va trebui sa scapam de operatiile de impartire. Aceasta se poate realiza usor, deoarece, in cadrul primei sume, $6$ se scrie ca fiind $2*3$ si cel putin unul din cei $3$ factori de la numarator este divizibil cu $2$ si cel putin unul este divizibil cu $3$. In mod similar, cel putin unul din cei doi factori de la numaratorul celei de-a doua sume este divizibil cu 2. Rezultatul cautat este $(R{~1~}-R{~2~}+P) mod P$.

Suma data se poate ca scrie ca <tex> \displaystyle\sum_{i = 1}^N i^2 </tex> - <tex> \displaystyle\sum_{i = 1}^N i </tex>. Prima suma este egala cu $N*(N+1)*(2*N+1)/6$. A doua suma este egala cu $N*(N+1)/2$. Se vor calcula restul impartirii primei sume la $P$ ({$R{~1~}$}) si restul impartirii celei de-a doua sume la $P$ ({$R{~2~}$}). Pentru aceasta va trebui sa scapam de operatiile de impartire. Aceasta se poate realiza usor, deoarece, in cadrul primei sume, $6$ se scrie ca fiind $2*3$ si cel putin unul din cei $3$ factori de la numarator este divizibil cu $2$ si cel putin unul este divizibil cu $3$. In mod similar, cel putin unul din cei doi factori de la numaratorul celei de-a doua sume este divizibil cu 2. Rezultatul cautat este $(R{~1~}-R{~2~}+P) mod P$.
Dupa acelasi rationament se dezvolta diferenta de sume si se obtine formula:
 
* Daca $N$ par: <tex> \displaystyle\ N*(N+1)*(N-1)/3</tex>;
* Daca $N$ impar: <tex> \displaystyle\ N*(N-1)*(N-2)/3 + N*(N-1)</tex>

h2. 'Numere':problema/numere