합이 같은 두 부분집합 (작은 입력)
시간 제한5초메모리 제한512 MB
원소가 20개인 각 집합에서 합이 같은 서로 다른 두 부분집합을 코드 규칙에 따라 출력하고 없으면 Impossible을 출력합니다.
문제
서로 다른 양의 정수 개로 이루어진 집합 가 주어진다. 원소의 합이 서로 같은, 공집합이 아닌 두 부분집합을 찾아라.
부분집합은 의 원소만으로 이루어진 집합이다. 두 부분집합의 원소가 완전히 같지 않으면 서로 다른 부분집합으로 본다. 두 부분집합이 같은 원소를 공유해도 된다.
입력
첫째 줄에 테스트 케이스의 개수 가 주어진다. 이어지는 개의 줄에 테스트 케이스가 한 줄씩 주어진다. 각 줄은 집합 의 원소 개수 으로 시작하고, 그 뒤에 의 원소인 서로 다른 양의 정수 개가 같은 줄에 이어진다.
제한
- 은 정확히 이다.
- 의 각 원소는 보다 작은 양의 정수다.
- 의 두 원소가 같은 값인 경우는 없다.
출력
각 테스트 케이스마다 먼저 "Case #x:"를 한 줄에 출력한다. 여기서 x는 테스트 케이스 번호이고 1부터 시작한다.
원소의 합이 같은 서로 다른 두 부분집합이 존재하면 두 부분집합을 한 줄에 하나씩 출력한다. 각 줄에는 그 부분집합의 원소를 증가하는 순서로 공백 하나씩 띄어 출력한다. 그런 두 부분집합이 없으면 "Impossible"을 한 줄에 출력한다.
조건을 만족하는 쌍이 여러 개일 수 있으므로 다음 규칙으로 정해지는 쌍 하나만 정답으로 인정한다. 의 원소를 증가하는 순서로 이라 하고, 공집합이 아닌 부분집합 의 코드를 로 정의한다. 합이 같은 서로 다른 두 부분집합의 쌍 가운데 두 코드의 최댓값이 가장 작은 쌍을 고르고, 그런 쌍이 여러 개면 그중 두 코드의 최솟값이 가장 작은 쌍을 고른다. 코드가 작은 부분집합을 먼저 출력한다.