BABTWR - Tower of Babylon

Apart from the Hanging Gardens the Babylonians (around 3000-539 b.c.) built the Tower of Babylon as well. The tower was meant to reach the sky, but the project failed because of a confusion of language imposed from much higher above.

For the 2638th anniversary a model of the tower will be rebuilt. n different types of blocks are available. Each one of them may be duplicated as many times as you like. Each type has a height y, a width x and a depth z. The blocks are to be stacked one upon eachother so that the resulting tower is as high as possible. Of course the blocks can be rotated as desired before stacking. However for reasons of stability a block can only be stacked upon another if both of its baselines are shorter.

Input

The number of types of blocks n is located in the first line of each test case. On the subsequent n lines the height yi, the width xi and the depth zi of each type of blocks are given. There are never more than 30 different types available.

There are many test cases, which come one by one. Input terminates with n = 0.

Edited: You can assume that max(xi, yi, zi) <= 2500.

Output

For each test case your program should output one line with the height of the highest possible tower.

Example

Sample input:
5
31 41 59
26 53 58
97 93 23
84 62 64
33 83 27
1
1 1 1
0

Sample output:
342
1

Added by:MichaƂ Czuczman
Date:2004-07-06
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Swiss Olympiad in Informatics 2004

hide comments
2020-08-23 13:21:52
easier version of box stacking algorithm.
2020-03-22 17:04:55
only 3 rotations are possible
because l * b * h = b * l * h
2020-02-07 16:20:10
good DP problem :) worth doing before searching for solution
2018-07-25 13:24:21
Quite tough if you haven't solved any longest increasing subsequence problem yet. Still worth a try before looking for hints/solution.
2018-06-13 18:52:38
Quite easy with Top-Down <3 :P!!!!Keep in mind the six rotations possible!!!
2018-01-19 09:13:37
6 rotations possible... good one.
2017-06-21 16:21:08
box stacking problem ..!!!
nice dp
2017-02-28 15:18:02
This can be solved in O(N log N), but it's a bit tricky. There is a pretty obvious O(N^2) solution and even more obvious O(N^3) that should still not TLE I think.

flyingduchman_ "As it's not an ad-hoc, you are unlikely to invent or discover the solution" - what a horribly self-limiting way of thinking. I discovered the O(N^2) solution without reading either of your suggestions and I think it's simple to come up with.

I was also well on the way to getting the O(N log N) before reading about the N log N LIS - i.e. I figured BST or some other query structure could be used to improve the O(N^2) and frankly, reading about LIS didn't help that much in figuring out how.
2016-12-23 05:49:40
Learn dp solution of LIS(longest increasing subsequence)first. Then learn "box stacking algorithm"-the problem is of. As it's not an ad-hoc, you are unlikely to invent or discover the solution
2016-11-09 16:02:17
3 rotations are possible if u keep (depth > width).
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.