#P2241. The Tower of Babylon
The Tower of Babylon
中文题面:
描述
也许你曾听说过巴比伦塔的传说。如今,这个故事的许多细节已被遗忘。因此,本着本次竞赛的教育性质,我们将为你讲述完整的故事:
巴比伦人拥有种类型的积木,每种类型的积木供应无限。每种类型的积木是一个尺寸为的长方体。积木可以重新定向,使得其任意两个维度决定底座的尺寸,另一个维度决定高度。
他们希望通过堆叠积木建造尽可能高的塔。问题是,在建塔时,一个积木只能放在另一个积木的顶部,且上方积木的两个底座维度必须严格小于下方积木对应的底座维度。这意味着,如果两个积木的底座尺寸相同,则不能堆叠。
你的任务是编写一个程序,计算巴比伦人用给定积木可以建造的最高塔的高度。
输入
输入包含一个或多个测试用例。每个测试用例的第一行是一个整数,表示接下来数据集中不同积木的数量。的最大值为。
接下来的行,每行包含三个整数,分别表示、和的值。
输入以终止。
输出
对于每个测试用例,输出一行,包含用例编号(从1开始顺序编号)和最高塔的高度,格式为:
"Case 用例编号: maximum height = 高度"
输入数据 1
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
输出数据 1
Case 1: maximum height = 40
Case 2: maximum height = 21
Case 3: maximum height = 28
Case 4: maximum height = 342