Baking bread is my favourite spare-time pursuit. I have a number of stainless steel mixing bowls with straight sides, a circular bottom and a wider circular top opening. Geometrically, my bowls are truncated circular cones and for this problem, the thickness of the metal may be disregarded.
I store these bowls stacked in the natural way, that is with a common vertical axis, and I stack them in an order that minimises the total height of the stack. Finding this minimum is the purpose of your program.
On the first line of the input is a positive integer, telling the number of test cases to follow. Each case starts with one line containing an integer n, the number of bowls (2 ≤ n ≤ 9). The following n lines each contain three positive integers h, r, R, specifying the height, the bottom radius and the top radius of the bowl, and r < R holds true. You may also assume that h, r, R < 1000.
For each test case, output one line containing the minimal stack height, truncated to an integer (note: truncated, not rounded).
2 2 60 20 30 40 10 50 3 50 30 80 35 25 70 40 10 90
70 55
Migrated from old NTUJ.
NWERC 2005
| No. | Testdata Range | Score |
|---|