巴比伦塔

Grade 100 Open Time Wednesday, 17 June 2020, 9:25 PM
Discount 0.8 Time Discount Wednesday, 17 June 2020, 9:25 PM
Allow late Yes Close Time Wednesday, 17 June 2020, 9:25 PM
Input file tower.in Output file tower.out

【题目描述】巴比伦塔(tower)UVA 437

有n种立方体,每种都有无穷多个。要求选一些立方体摞成一座尽量高的塔,使得每个立方体的底面长宽分别严格小于它下方立方体的底面长宽。

【输入格式】

输入包括一组或多组数据,每组数据第一行为一个整数n(n≤30),表示立方体种数,随后n行中,每行三个整数,表示立方体的长、宽和高。全部数据输入结束以一行0表示。

【输出格式】

每行一组数据的答案,输出格式见样例。

【输入样例】

1

10 20 30

2

6 8 10

5 5 5

7

1 1 1

2 2 2

3 3 3

4 4 4

5 5 5

6 6 6

7 7 7

5

31 41 59

26 53 58

97 93 23

84 62 64

33 83 27

0

【输出样例】

Case 1: maximum height = 40

Case 2: maximum height = 21

Case 3: maximum height = 28

Case 4: maximum height = 342