UVa 437 - The Tower of Babylon

// UVa 437 - The Tower of Babylon

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>
using namespace std;

#define datatype unsigned long long int

struct triad {
	datatype x, y, z;
};

bool operator <(triad a, triad b) {
	return a.x < b.x || a.x == b.x && a.y < b.y || a.x == b.x && a.y == b.y && a.z < b.z || a.x == b.x && a.y == b.y && a.z == b.z;
}

int main() {
	int t = 0;
	int n;
	cin >> n;
	while (n) {
		t++;
		triad a[30];
		for (int i = 0; i < n; i++) {
			datatype x, y, z;
			cin >> x >> y >> z;
			a[i].x = min(min(x, y), z);
			a[i].z = max(max(x, y), z);
			a[i].y = x + y + z - a[i].x - a[i].z;
		}
		sort(a, a + n);
		triad b[90];
		int j = 0;
		for (int i = 0; i < n; i++) {
			b[j].x = a[i].x;
			b[j].y = a[i].y;
			b[j].z = a[i].z;
			j++;
			b[j].x = a[i].y;
			b[j].y = a[i].z;
			b[j].z = a[i].x;
			j++;
			b[j].x = a[i].x;
			b[j].y = a[i].z;
			b[j].z = a[i].y;
			j++;
		}
		n *= 3;
		sort(b, b + n);
		datatype sol = 0;
		datatype T[90];
		for (int i = 0; i < n; i++) {
			T[i] = 0;
			for (int j = 0; j < i; j++)
				if (b[j].x < b[i].x && b[j].y < b[i].y && T[j] > T[i]) {
					T[i] = T[j];
				}
			T[i] += b[i].z;
			if (T[i] > sol)
				sol = T[i];
		}
		printf("Case %d: maximum height = %llu\n", t, sol);

		cin >> n;
	}

	return 0;
}