# CEOI 1996 example solution

I would like to know this examples's solution. I write a heuristic algorithm for this but it is not good.

Here is the example: (cutting rectangle)
http://www.oi.edu.pl/php/ceoi2004.php?module=show&file=history#1996-22]

• : I would like to know this examples's solution. I write a heuristic algorithm for this but it is not good.
:
: Here is the example: (cutting rectangle)
: http://www.oi.edu.pl/php/ceoi2004.php?module=show&file=history#1996-22]
:

The problem is, as usual in those kind of competitions, not the programming but rather understanding wtf they mean with their poorly formulated text:

[italic]"Cutting can be performed with a cutting machine that can cut only from side to side across, parallel with one side of the rectangle."[/italic]

The description is not clear, the above can mean [italic]anything[/italic]. If I take a 6x5 rectangle and cut it up parallell with one side (any side?), yeah then I can get 30 squares of size 1x1... which is not what they want you to answer. What they are telling you is "make a program that does something with rectangles and hopefully you will get the output expected".
• I wolud like the optimal solution where the squares number minimal.
I wrote a program where I divide with the less side. But this is not the optimal solution.

For example when the rectangle is 5x6 my program divide it 1 5x5 and 5 1x1 squares. But the optimal solution is 3 2x2 and 2 3x3 squares.

• : I wolud like the optimal solution where the squares number minimal.
: I wrote a program where I divide with the less side. But this is not the optimal solution.
:
: For example when the rectangle is 5x6 my program divide it 1 5x5 and 5 1x1 squares. But the optimal solution is 3 2x2 and 2 3x3 squares.
:

The optimal solution is 30 1x1 squares. Which was my point, the question is poorly formulated.

As for the code, show what you have made so far and I'll have a look at it.
• I wolud like to know the MINIMUM NUMBER of the squares not the maximum.
5x6 rectangle -> yes I divide it 30 1x1 but this is the maximum
-> 2 pieces of 3x3 and 3 pieces of 2x2 is the minimum
• : I wolud like to know the MINIMUM NUMBER of the squares not the maximum.
: 5x6 rectangle -> yes I divide it 30 1x1 but this is the maximum
: -> 2 pieces of 3x3 and 3 pieces of 2x2 is the minimum
:

Yes, I understand that. Now where is your code?