Editorial for COCI '07 Contest 2 #2 Crne

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.

If Mirko makes $H$ ~H~ horizontal and $V$ ~V~ vertical cuts, Slavko's board will fall apart into $(H+1) \cdot (V+1)$ ~(H+1) \cdot (V+1)~ pieces.

The first solution uses two nested for-loops to try all possible values of $H$ ~H~ and $V$ ~V~ (such that their sum is not greater than $N$ ~N~) and outputs the largest product.

The second solution is to notice that it never makes sense to make less than $N$ ~N~ cuts, and loops over all values of $H$ ~H~, and uses the expression $N-H$ ~N-H~ for $V$ ~V~.

The third solution doesn't use any loops, instead observing that the product will be the largest if $H$ ~H~ and $V$ ~V~ are as close as possible. The actual expressions are $H = \lfloor \frac N 2 \rfloor$ ~H = \lfloor \frac N 2 \rfloor~, $V = \lfloor \frac{N+1} 2 \rfloor$ ~V = \lfloor \frac{N+1} 2 \rfloor~.

Comments

There are no comments at the moment.