로그 집합 (스몰)

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

요약
모든 부분집합 합 빈도에서 원래 정수 다중집합을 복원하고 동률은 정렬 순서가 앞선 것으로 정합니다.
난이도

보통10점 중 7점

유형
백트래킹, 정렬, 해시맵
정답자
아직 제출이 없습니다

문제

집합 SS의 멱집합은 SS의 모든 부분집합을 모은 것이다. 공집합과 SS 자신도 포함한다. 집합에서 멱집합을 만들기는 쉽지만, 이 문제에서는 반대 방향으로 간다.

정수로 이루어진 다중집합 SS에서 출발한다. 원소가 서로 달라야 할 필요는 없다. SS의 부분집합을 모두 구한 다음 각 부분집합을 그 부분집합의 원소 합으로 바꾸면 새로운 다중집합 S′S'이 나온다. 예를 들어 S={−1,1}S = \lbrace -1, 1 \rbrace이면 부분집합은 {}\lbrace \rbrace, {−1}\lbrace -1 \rbrace, {1}\lbrace 1 \rbrace, {−1,1}\lbrace -1, 1 \rbrace이고, 따라서 S′={0,−1,1,0}S' = \lbrace 0, -1, 1, 0 \rbrace이다. S′S'에는 같은 값이 여러 번 들어갈 수 있어서, SS의 원소가 NN개면 S′S'의 원소는 언제나 정확히 2N2^N개다.

S′S'에 들어 있는 값과 각 값의 등장 횟수가 주어진다. 원래의 SS를 복원하라. 그런 SS는 반드시 존재한다. 같은 S′S'을 만드는 다중집합이 여럿이면 그중 가장 앞서는 것이 답이다. 크기가 같은 두 다중집합 S1S_1과 S2S_2 중 어느 쪽이 앞서는지는 각각을 비내림차순으로 정렬한 뒤 값이 처음으로 달라지는 자리를 보고 정한다. 그 자리의 값이 더 작은 쪽이 앞선다.

입력

첫째 줄에 테스트 케이스의 개수 TT가 주어진다. 각 테스트 케이스는 세 줄이다. 첫 줄에 정수 PP가 주어지고, 다음 두 줄에는 각각 PP개의 정수가 공백으로 구분되어 주어진다. 앞의 줄은 S′S'에 등장하는 서로 다른 값 E1,E2,…,EPE_1, E_2, \dots, E_P를 오름차순으로 나열한 것이고, 뒤의 줄은 각 값이 등장하는 횟수 F1,F2,…,FPF_1, F_2, \dots, F_P다. 즉 값 EiE_i는 S′S'에 FiF_i번 들어 있다.

제한

  • 1≤T≤1001 \le T \le 100
  • 1≤P≤100001 \le P \le 10000
  • Fi≥1F_i \ge 1
  • SS의 원소 개수는 1개 이상 20개 이하다. 따라서 F1+F2+⋯+FPF_1 + F_2 + \dots + F_P는 2의 거듭제곱이다.
  • −108≤Ei≤108-10^8 \le E_i \le 10^8

출력

각 테스트 케이스마다 한 줄에 Case #x:를 출력하고 (xx는 1부터 시작하는 테스트 케이스 번호), 이어서 원래 다중집합 SS의 원소를 비내림차순으로 공백 한 칸씩 띄워 출력한다. 입력처럼 값과 횟수를 두 줄로 나누지 말고 SS의 원소를 그대로 나열한다.

예제2

  1. 예제 1

    입력
    5
8
0 1 2 3 4 5 6 7
1 1 1 1 1 1 1 1
4
0 1 2 3
1 3 3 1
4
0 1 3 4
4 4 4 4
3
-1 0 1
1 2 1
5
-2 -1 0 1 2
1 2 2 2 1
    예상 출력
    Case #1: 1 2 4
Case #2: 1 1 1
Case #3: 0 0 1 3
Case #4: -1 1
Case #5: -2 1 1

  2. 예제 2

    입력
    5
1
0
2
2
0 5
1 1
2
-7 0
1 1
2
0 100000000
1 1
2
-100000000 0
1 1
    예상 출력
    Case #1: 0
Case #2: 5
Case #3: -7
Case #4: 100000000
Case #5: -100000000