Hide

Problem A
Adolescent Architecture

\includegraphics[scale=0.07]{building-blocks.jpg}

Little Peter is building a stack out of his toy blocks. He is using two kinds of blocks – cubes and cylinders – and wants to stack all of them into a single tower, where each block other than the topmost block has a single block standing on it. In order for the tower to be stable, the outline of each block needs to be fully contained within the outline of the block below when looking at the tower from above (the outlines are allowed to touch). Is it possible to construct such a tower, and if so, in which order do the blocks need to be stacked?

Input

The input consists of:

  • One line with an integer $n$ ($1 \le n \le 100$), the number of blocks.

  • $n$ lines, each with the description of a block. The description consists of a string giving the type of block (cube or cylinder) and an integer $a$ ($1 \le a \le 1\, 000$) giving the size of the block – if the block is a cube then $a$ is its side length, and if it is a cylinder then $a$ is the radius of its base (note that the height of the cylinder does not matter).

Output

If there is no way to construct the tower, output impossible. Otherwise output $n$ lines, giving the order in which to stack the blocks from top to bottom.

Sample Input 1 Sample Output 1
3
cube 7
cube 11
cylinder 5
cube 7
cylinder 5
cube 11
Sample Input 2 Sample Output 2
2
cube 5
cylinder 3
impossible
Sample Input 3 Sample Output 3
3
cube 4
cylinder 2
cube 4
cylinder 2
cube 4
cube 4
CPU Time limit 1 second
Memory limit 1024 MB
Statistics Show
Author
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in