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 horizontal and V vertical cuts, Slavko's board will fall apart into (H+1) \cdot (V+1) pieces.

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

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

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


There are no comments at the moment.