시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 28 20 12 66.667%

문제

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?

입력

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

출력

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.

예제 입력 1

3
cube 7
cube 11
cylinder 5

예제 출력 1

cube 7
cylinder 5
cube 11

예제 입력 2

2
cube 5
cylinder 3

예제 출력 2

impossible

예제 입력 3

3
cube 4
cylinder 2
cube 4

예제 출력 3

cylinder 2
cube 4
cube 4

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > German Collegiate Programming Contest > GCPC 2020 A번

  • 문제를 만든 사람: Paul Wild