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.
Please help.

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

Comments

  • : I would like to know this examples's solution. I write a heuristic algorithm for this but it is not good.
    : Please help.
    :
    : 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?
Sign In or Register to comment.

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories