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:
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:
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.