합이 같은 두 부분집합 (작은 입력)

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

요약
원소가 20개인 각 집합에서 합이 같은 서로 다른 두 부분집합을 코드 규칙에 따라 출력하고 없으면 Impossible을 출력합니다.
난이도

보통10점 중 5점

유형
완전 탐색, 해시맵
정답자
아직 제출이 없습니다

문제

서로 다른 양의 정수 NN개로 이루어진 집합 SS가 주어진다. 원소의 합이 서로 같은, 공집합이 아닌 두 부분집합을 찾아라.

부분집합은 SS의 원소만으로 이루어진 집합이다. 두 부분집합의 원소가 완전히 같지 않으면 서로 다른 부분집합으로 본다. 두 부분집합이 같은 원소를 공유해도 된다.

입력

첫째 줄에 테스트 케이스의 개수 TT가 주어진다. 이어지는 TT개의 줄에 테스트 케이스가 한 줄씩 주어진다. 각 줄은 집합 SS의 원소 개수 NN으로 시작하고, 그 뒤에 SS의 원소인 서로 다른 양의 정수 NN개가 같은 줄에 이어진다.

제한

  • 1≤T≤101 \le T \le 10
  • NN은 정확히 2020이다.
  • SS의 각 원소는 10510^5보다 작은 양의 정수다.
  • SS의 두 원소가 같은 값인 경우는 없다.

출력

각 테스트 케이스마다 먼저 "Case #x:"를 한 줄에 출력한다. 여기서 x는 테스트 케이스 번호이고 1부터 시작한다.

원소의 합이 같은 서로 다른 두 부분집합이 존재하면 두 부분집합을 한 줄에 하나씩 출력한다. 각 줄에는 그 부분집합의 원소를 증가하는 순서로 공백 하나씩 띄어 출력한다. 그런 두 부분집합이 없으면 "Impossible"을 한 줄에 출력한다.

조건을 만족하는 쌍이 여러 개일 수 있으므로 다음 규칙으로 정해지는 쌍 하나만 정답으로 인정한다. SS의 원소를 증가하는 순서로 s1<s2<⋯<s20s_1 < s_2 < \cdots < s_{20}이라 하고, 공집합이 아닌 부분집합 AA의 코드를 code⁡(A)=∑si∈A2i−1\operatorname{code}(A) = \sum_{s_i \in A} 2^{i-1}로 정의한다. 합이 같은 서로 다른 두 부분집합의 쌍 가운데 두 코드의 최댓값이 가장 작은 쌍을 고르고, 그런 쌍이 여러 개면 그중 두 코드의 최솟값이 가장 작은 쌍을 고른다. 코드가 작은 부분집합을 먼저 출력한다.

예제2

  1. 예제 1

    입력
    2
    20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
    20 120 266 858 1243 1657 1771 2328 2490 2665 2894 3117 4210 4454 4943 5690 6170 7048 7125 9512 9600
    
    예상 출력
    Case #1:
    1 2
    3
    Case #2:
    1243 1771
    120 2894
    
  2. 예제 2

    입력
    1
    20 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71
    
    예상 출력
    Case #1:
    2 3
    5