h3. problema usoara, clasele 9-10

Se observa ca figura se obtine dintr-un patrat de latura $radical(N)$, la care se mai adauga niste patratele pe margini, solutia fiind $4*radical(N)$ pentru $N$ patrat perfect, $4*radical(N)+2$ pentru cazul in care acoperim maxim o latura cu patratele sau $4*radical(N)+4$ pentru cazul in care acoperim maxim 2 laturi cu patratele.

Vom nota cu P{~k~}, perimetrul minim al figurii ce contine $k$ patratele de latura unitate. Vom trata intai cazul in care $N$ este patrat perfect pornind de la $N = 1$ pentru care $P{~1~} = 1$. Pentru $N = 4$, construind toate figurile posibile se observa cea de perimetru minim are forma unui patrat cu latura $radical(N)$, deci $P{~4~} = 4*radical(N)$. Continuand procedeul, se demonstreaza cu ajutorul principiului inducitei matematice ca $P{~t~} = 4*radical(t)$, oricare ar fi $t$ patrat perfect.
Pentru al doilea caz, cel in care $N$ nu este patrat perfect, figura noastra porneste tot de la un patrat de latura $radical(N)$. Este evident faptul ca pentru ca $P{~N~}$ sa fie minim, trebuie ca pe marginile figurii sa avem cat mai putine patratele carora li se aduna doua laturi la perimetru (cu alte cuvinte trebuie sa avem cat mai putine patratele care sa formeze colturi). Va trebui, deci, sa adaugam pe marginile patratului format $N-[radical(N)]*[radical(N)]$ (cu $[x]$ s-a notat partea intreaga a lui $x$) patratele. Astfel solutia devine $4*radical(N)$ pentru $N$ patrat perfect, $4*radical(N)+2$ pentru cazul in care acoperim maxim o latura cu patratele sau $4*radical(N)+4$ pentru cazul in care acoperim maxim 2 laturi cu patratele.

O solutie care calcula aceste valori in O({$N$}) nu ar fi obtinut punctaj maxim.
h2. Mall