welcome: please sign in

Upload page content

You can upload content for the page named below. If you change the page name, you can also upload content for another page. If the page name is empty, we derive the page name from the file name.

File to load page content from
Page name

location: FinalProblemDescriptions / Packing


Problem Description

Given a rectangular area of a known dimension and a set of squares, each of which has a known dimension, the problem is to pack all the squares into the rectangular area such that no two squares overlap each other. There can be wasted spaces in the rectangular area.

The rectangular area forms a coordinate plane where the left upper corner of the area is the origin, the top edge is the x-axis, and the left edge is the y-axis.


Input format

The input contains a fact area(W,H) which specifies the dimension of the rectangular area (the top edge is W units and the left edge is H units), a fact max_square_num(N) which gives the number of squares to be packed (the squares are numbered from 1 to N), and a fact square(I,Size) for each I between 1 and N which gives the size of the square numbered I.

Output format

The output should contain a fact pos(I,X,Y) for each square which gives the coordinates of the left upper corner of the square in the rectangular area. Let W be the width and H the height of the rectangular area, and Size be the size of the square. Then the coordinates X and Y must satisfy:

     0 =< X =< W-Size 
     0 =< Y =< H-Size


For the following input


one possible solution is: