[Problem D | 1995 Western Europe problem set | Ed's programming contest problem archive | my home page]

Western European Regional

This is an example of one of his buildings. It was built on a table that could contain 4×4 block stacks.

He liked drawing too. To record his block buildings for future generations, he would draw them on paper. Since drawing a three-dimensional block building just was too hard for him, he made two drawings of a building: one straight from the front (you could only see the front of the blocks), and one from the right (you could only see the right side of the blocks). The drawings were in fact two-dimensional projections of the block building, showing only its outline on the front or on the right side.

These are the drawings he made of the building shown above.

He thought that such a pair of drawings would give enough information to be able to re-build the block building later (but he never tried it).

Years later, looking again at the drawings, he realized that this was not the case: from most
pairs of drawings, he was able to construct more than one building that had the same outlines (front
and right side) as the original one. He found out that from every (front, side)-pair of drawings
that he had made, he could construct a 'minimal' building, one that has the same outlines as the
original building and contains a minimal number of blocks *N* (so it was not possible to construct a
building with the same outlines with less than *N* blocks). Furthermore, he could add more blocks
to this minimal building, so that the outlines remained the same, up to the point that he had
added *M* (*M* >= 0) blocks and he had a 'maximal' building, one that still had the same outlines
as his minimal one, and adding one extra block would result in a building with a different outline
(so there are no buildings with the same outlines that contain more than *N* + *M* blocks).

As an example, these are minimal and maximal buildings for the drawings shown above. In
this case, *N* = 7 and *M* = 10.

Minimal Building | Maximal Building |

Matty started determining the *N* and *M* for every pair of drawings he had made, but soon he
found this task to be tedious. Now he asks *you* to write a program that does the job for him!

Matty needs at leastNblocks, and can add at mostMextra blocks.

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

Matty needs at least 7 blocks, and can add at most 10 extra blocks. Matty needs at least 1 blocks, and can add at most 0 extra blocks.

This page maintained by Ed Karrels.

Last updated January 3, 1998