Sticks

시간 제한3초메모리 제한512 MB

요약
막대기 12개의 길이가 주어질 때 각 막대기를 최대 한 번씩 사용해 만들 수 있는 삼각형의 최대 개수를 구하고 그 구성을 출력한다.
난이도

보통10점 중 6점

유형
그리디, 정렬, 완전 탐색, 구현
정답자
아직 제출이 없습니다

문제

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.

제한

  • 1 ≤ T ≤ 6000
  • 1 ≤ l1, l2, . . . , l12 ≤ 109

예제1

  1. 예제 1

    입력
    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