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!