## Welcome To SDIBT ACM-ICPC Online Judge

VIRTUAL JUDGE Recent Contest F.A.Qs Discuss Home ProblemSet Status Ranklist 19 Contest LoginRegister Exam
2017 ACM 集训队预选排名~      报名入口

Problem 1083. -- Tower of Cubes

## Tower of Cubes

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 14  Solved: 0
[Submit][Status][Discuss]

## Description

You are given N colorful cubes, each having a distinct weight. Cubes are not monochromatic - indeed, every face of a cube is colored with a different color. Your job is to build the tallest possible tower of cubes subject to the restrictions that (1) we never put a heavier cube on a lighter one, and (2) the bottom face of every cube (except the bottom one) must have the same color as the top face of the cube below it.

## Input

The input may contain several test cases. The first line of each test case contains an integer N ( 1<=N<=500) indicating the number of cubes you are given. The ith of the next N lines contains the description of the ith cube. A cube is described by giving the colors of its faces in the following order: front, back, left, right, top, and bottom face. For your convenience colors are identified by integers in the range 1 to 100. You may assume that cubes are given in increasing order of their weights; that is, cube 1 is the lightest and cube N is the heaviest. The input terminates with a value 0 for N.

## Output

For each case, start by printing the test case number on its own line as shown in the sample output. On the next line, print the number of cubes in the tallest possible tower. The next line describes the cubes in your tower from top to bottom with one description per line. Each description gives the serial number of this cube in the input, followed by a single white­space character and then the identification string (front, back, left, right, top, or bottom of the top face of the cube in the tower. There may be multiple solutions, but any one of them is acceptable. Print a blank line between two successive test cases.

```3
1 2 2 2 1 2
3 3 3 3 3 3
3 2 1 1 1 1
10
1 5 10 3 6 5
2 6 7 3 6 9
5 7 3 2 1 9
1 3 3 5 8 10
6 6 2 2 4 4
1 2 3 4 5 6
10 9 8 7 6 5
6 1 2 3 4 7
1 2 3 3 2 1
3 2 1 1 2 3
0

```

## Sample Output

```Case #1
2
2 front
3 front

Case #2
8
1 bottom
2 back
3 right
4 left
6 top
8 front
9 front
10 top

```

## Source

[Submit][Status][Discuss]

HOME Back

한국어 中文 English
All Copyright Reserved 2008-2010 SDIBT TEAM
GPL2.0 2003-2010 HUSTOJ Project TEAM