Want to try solving this problem? You can submit your code online if you log in or register.

**Input File:** `paintin.txt`

**Output File:** `paintout.txt`

**Time Limit:** 1.25 seconds

You are working part time in the art gallery. On of your jobs is to place paintings on a wall in the gallery. The gallery is rather short on space, and needs to pack the paintings tightly on a single wall in the gallery. Each painting and the wall itself has dimensions which are an integer number of millimeters.

There are some rules about where paintings can be placed:

- Paintings must be placed with their sides parallel to the sides of the wall, and in the correct orientation.
- Paintings cannot overlap - the patrons need to see the whole painting to appreciate it.
- Paintings must be hung in the order they arrive.
- Paintings must be placed as far to the left of the wall as possible when they are hung.
- Paintings must be hung as low as possible, without breaking rule 4.

The x-coordinate of a painting is the distance (in millimeters) of the left edge of the painting from the left edge of the wall. The y-coordinate is the distance (in millimeters) of the bottom of the painting from the bottom of the wall.

Thus rule 4 says that paintings must be given the least x-coordinate possible when they arrive, and rule 5 says that paintings must be given the least y-coordinate possible which doesn't increase the x-coordinate.

The first line of input shall contain two integers *W* and *H*,
separated
by a single space. These give the width and height (respectively) of the
wall on which the paintings are to be hung, measured in millimeters.

Each following line of input shall contain two integers *w_i* and
*h_i*,
separated by a single space. These give the width and height (respectively)
of the next painting to be hung, measured in millimeters.

The input shall be terminated by a line consisting of two 0s (zeroes) separated by a single space.

You are guaranteed that:

- 1 <=
*W*<= 30,000 - 1 <=
*H*<= 30,000 - For each painting
*i*, 1 <=*w_i*<=*W*. - For each painting
*i*, 1 <=*h_i*<=*H*. - All paintings can be hung on the wall by following the rules.

For each painting in the input (each line after the first), your program
shall output a single line consisting of two integers *x_i* and *y_i*,
separated by a single space. These give the x-coordinate and y-coordinate
of the corresponding painting when placed according to the rules.

5 4 3 3 2 2 4 1 1 2 1 1 0 0

0 0 3 0 0 3 4 2 3 2

For each test case, let *n* be the number of paintings to be placed.
If your program correctly places *r* of the paintings for this case, it
shall be awarded *r*/*n* of the available marks for the test case.

Privacy
statement

© Australian Mathematics Trust 2001-2021

Page generated: 21 October 2021, 6:41pm AEDT