ZOJ Problem Set - 3285
Once upon a time, there was a magical land. People living on the magical land had great creativity, as a very good example of their remarkable creativity, the large amount of different kinds of towers were all beautiul and useful. We modern people can imagine the magnificent scenery, but time flies, no matter how wonderful the towers of magical land were, things always ended into dust.
But there is still some way to know something about the ancient scenery, our archaeological team finally find a tower in the ruins. It was thin, and they think that it can be called as a wall. But from the ancient record, they find out that towers of the ancient magical land are just like the one.
After some detailed research, they find out that their explore of the ancient tower may cause a huge damage to it, the tower is airslaking, every brick of it is lossing weight capacity. Now they want to know before the whole tower's collapse, how many hours they have.
Here is some detail about the tower. It is formed by bricks, every brick is a 1 * 1 * 2 one, and the bricks formed the tower layer by layer. We know that tower has a thickness of 1, thus look from the front, the tower is formed by some 1 * 2 rectangles. Consider every two adjacent bricks, if they are not in the same layer, the middle of the brick which is upper must be strictly on the left end or the right end of the other brick. For every brick, if there is only one brick can sustain it, the total weight it received from the upper bricks and its self weight will be sustained by the only lower brick. And if there are two bricks can sustain it, half of the total weight it received from the upper bricks and its self weight will be sustained by both of the two lower bricks.
Now we know that all bricks are the same, they all have a weight W, and weight capacity C, and every hour the bricks' weight capacity will decrease D, but the weight capacity cannot be a negative number. If a brick's sustaining weight(exclude its self weight) is large than its weight capacity, it will become dust and can be regard as disappeared. And all the things you have to concerned about is the time in this problem is discrete.
This picture shows a sample:
There are several test cases.
In each case, there will be four numbers in the first line, N(integer, 1 <= N <= 1000), which represent the number of bricks; W(integer, 1 <= W <= 1000); C(integer, 1 <= C <= 1000); D(integer, 1 <= D <= 1000).
The next N lines(thus the line 2 to N + 1) describe the bricks, line i(from 2 to N + 1) has two integers xi - 1 and yi - 1(0 <= xi - 1, yi - 1 <= 200), which descripted the coordinate of brick's left bottom. The ground's x-coordinate is 0.The input is guaranteed to be valid and there is no overlap of bricks.
For each test case, output the first time that there are some brick disappeared and how many bricks disappeared at this very time in one line, and separated them with a single space. If there is no brick to disappear, just output a single -1 instead of these two numbers.
7 10 50 10 0 2 0 4 1 1 1 3 1 5 2 0 2 4 3 10 20 10 0 2 0 4 0 6
3 2 -1
Author: FAN, Yuzhe
Source: ZOJ Monthly, December 2009