| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 512 MB | 38 | 13 | 10 | 40.000% |
Bob has 12 sticks of lengths l1, l2, . . . , l12. He wants to use some sticks to form triangles as many as possible. Each triangle can be built by three different sticks la, lb, lc such that la + lb > lc, la + lc > lb and lb + lc > la. If each stick can be used for at most one triangle, how many triangles can he build at most? Also, could you please find a way to build them all?
The input contains several test cases. The first line contains an integer T indicating the number of test cases. The following describes all test cases. For each test case:
The only line contains twelve integers l1, l2, . . . , l12.
For each test case, firstly output a line containing “Case #x: m” (without quotes), where x is the test case number starting from 1, and m is the maximum number of triangles that can be built.
Then, output m lines, each line of which contains three integers, representing three side lengths of a triangle.
If there are many optimal solutions, please output any of them. Note that every stick for each test case can be used at most once, and every two adjacent integers in a line of the output should be separated by one space.
5 1 2 1 3 1 4 1 5 1 6 1 7 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 5 8 13 21 34 55 89 144 233 2 3 6 15 27 59 72 83 121 159 201 234 2 2 4 8 16 32 64 128 256 512 1024 1281
Case #1: 4 1 1 1 4 3 2 1 1 1 6 7 5 Case #2: 3 6 5 4 10 12 11 9 8 7 Case #3: 0 Case #4: 2 83 121 72 234 159 201 Case #5: 1 1024 1281 512