Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-10-11 22:33:58.
Revizia anterioară   Revizia următoare  

Solutii Happy Coding 1

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 2×2, cate unul pentru fiecare latura a poligonului intersectie, ce contin coordonatele celor 2 puncte ale fiecarei laturi.

Bile

Problema se rezolva folosind structura de date numita multimi disjuncte. Se va inversa sensul operatiilor date, parcurgandu-le de la sfarsit care inceput, si considerand ca ele reprezinta operatii de adaugare a cate unei bile, si nu de eliminare a bilelor. Se va mentine pe parcurs valoarea maxima a componentelor conexe formate.

Muzeu

Problema se rezolva folosind algoritmul lui Lee, considerand ca se pleaca simultan din toate pozitiile paznicilor. Varianta "clasica" a algoritmului porneste de la o singura pozitie. Aceasta pozitie de start este adaugata intr-o coada. Apoi, fiecare element al cozii este expandat pe rand, putand adauga noi elemente in coada, vecine cu acesta. Singura diferenta fata de varianta "clasica" este ca la inceput se introduc in coada toate pozitiile corespunzatoare cate unui paznic.

Transport

Se va cauta binar capacitatea minima a camionului. Pentru o capacitate fixata C, se va folosi un algoritm greedy pentru a determina numarul minim X de transporturi ce trebuie efectuate. Acest algoritm greedy va lua in primul transport un numar maxim de saltele din varful stivei, cu conditia ca suma volumelor acestora sa nu depaseasca valoarea C. La al doilea transport va face acelasi lucru, pornind de la salteaua ramasa in varful stivei s.a.m.d. Daca numarul de transporturi determinat X este mai mic sau egal cu K, atunci se poate incerca o capacitate mai mica; in caz contrar, se va incerca o capacitate mai mare.

Suma

Suma data se poate ca scrie ca  \displaystyle\sum_{i = 1}^N i^2 -  \displaystyle\sum_{i = 1}^N i . 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 (R1) si restul impartitii celei de-a doua sume la P (R2). 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 (R1-R2+P) mod P.

Numere