Algoge Judge

Editorial for Obim Pravougaonika

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: milisav

Pretpostavimo da možemo da konstruišemo dva pravougaonika, jedan sa stranicama $a$ $a$ i $b$ $b$ , i drugi sa stranicama $c$ $c$ i $d$ $d$ . Pretpostavimo da je $|a-b| \le |c-d|$ $|a-b| \le |c-d|$ . Primetimo da je $a \cdot b = c \cdot d$ $a \cdot b = c \cdot d$ , jer ta dva pravougaonika su napravljena koristeći iste ploče i imaju površinu $P = \frac{N \cdot (N+1)}{2}$ $P = \frac{N \cdot (N+1)}{2}$ . Zbog toga:

$|a-b| \le |c-d| \implies (a-b)^2 \le (c-d)^2 \implies a^2 - 2 a b + b^2 \le c^2 - 2 c d + d^2 \implies$

$\implies a^2-2 a b + b^2 + 4 P \le c^2 - 2 c d + d^2 + 4 P \implies a^2 + 2 a b + b^2 \le c^2 + 2 c d + d^2 \implies (a+b)^2 \le (c+d)^2 \implies a+b \le c+d$

Dakle, kako je $a+b \le c+d$ $a+b \le c+d$ , to je obim prvog pravougaonika manji od obima drugog pravougaonika. Dakle, težimo da smanjimo dužinu duže stranice. Razmatrajmo slučajeve:

$N$ $N$ je paran broj. Primetimo da je dužina jedne stranice pravougaonika bar $N$ $N$ , jer imamo ploču dimenzija $1 \times N$ $1 \times N$ , kao i da možemo da napravimo pravougaonik dimenzija $(N+1) \times \frac{N}{2}$ $(N+1) \times \frac{N}{2}$ . Ovo možemo da postignemo tako što u prvi red stavimo ploče $1 \times 1$ $1 \times 1$ i $1 \times N$ $1 \times N$ , u drugi red ploče $1 \times 2$ $1 \times 2$ i $1 \times (N-1),...,$ $1 \times (N-1),...,$ u red $\frac{N}{2}$ $\frac{N}{2}$ ploče $1\times \frac{N}{2}$ $1\times \frac{N}{2}$ i $1 \times (\frac{N}{2}+1)$ $1 \times (\frac{N}{2}+1)$ . Primetimo da je tada stranica dužine $N+1$ $N+1$ duža od stranice $\frac{N}{2}$ $\frac{N}{2}$ , ali i da ne možemo da napravimo pravougaonik sa stranicom $N$ $N$ , jer bi to značilo da mu je druga stranica dužine $\frac{N+1}{2}$ $\frac{N+1}{2}$ , što nije ceo broj. U ovom slučaju, odgovor je: $3N + 2$ $3N + 2$ . Na slici ispod je primer rasporeda za $N=8$ $N=8$ :

$N$ $N$ je neparan broj. Primetimo da je, slično prethodnom slučaju, dužina jedne stranice pravougaonika bar $N$ $N$ , jer imamo ploču dimenzija $1 \times N$ $1 \times N$ , kao i da možemo da napravimo pravougaonik dimenzija $N \times \frac{N+1}{2}$ $N \times \frac{N+1}{2}$ . Ovo možemo da postignemo tako što u prvi red stavimo ploču $1 \times N$ $1 \times N$ u drugi red stavimo ploče $1 \times 1$ $1 \times 1$ i $1 \times (N-1)$ $1 \times (N-1)$ , u treći red ploče $1 \times 2$ $1 \times 2$ i $1 \times (N-2),...,$ $1 \times (N-2),...,$ u red $\frac{N+1}{2}$ $\frac{N+1}{2}$ ploče $1\times \frac{N-1}{2}$ $1\times \frac{N-1}{2}$ i $1 \times \frac{N+1}{2}$ $1 \times \frac{N+1}{2}$ . U ovom slučaju, odgovor je: $3N + 1$ $3N + 1$ . Na slici ispod je primer rasporeda za $N=7$ $N=7$ :

Vremenska složenost je $O(1)$ $O(1)$ .

Comments

5

MladenP commented on April 5, 2020, 9:56 p.m.

Vrlo kul zadatak, Miki!

Nadam se ovakvom kvalitetu zadataka i na buducim takmicenjima! (sem treceg on budi komunistu u meni)
5

Pajaraja commented on April 5, 2020, 8:11 p.m. ← edited →

Sjajan editorial, Miki!

Hvala Mikiju i sjajnim DMOJ i Algoge platformama!