| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 256 MB | 303 | 61 | 52 | 22.807% |
세계 과학의 날을 기념하여 LG 대학에서 일반인들이 참여할 수 있는 재미있는 과학 실험 이벤트를 준비했다. 많은 참가자가 예상되어 대학내 세 개의 큰 강당을 실험실로 활용하기로 하였다. 강당의 이름은 A, B, C이고, 실험실의 이름도 강당의 이름을 이용한다.
참여자 모두의 안전을 위해 각 강당에는 충분한 수의 실험 조교들이 배치될 예정이지만 만일의 사태에 대비하여 보조 조교도 배치하려고 한다.
보조 조교에 지원한 사람은 총 n명이고, 강당 A, B, C에 각각 최대 nA, nB, nC 명의 보조 조교를 배치하려고 한다. 한 사람은 최대 한 곳의 실험실에만 배정할 수 있고, 각 사람마다 선호하는 강당이 다르기 때문에 이를 고려하여 배치해야 한다.
예를 들어, n = 4, nA = nB = nC = 1 인 경우를 생각해보자. 사람은 1부터 4까지 번호가 매겨져 있다.
이 경우, nC = 1 이기 때문에 2번과 3번을 모두 실험실 C에 배정할 수는 없고, 둘 중 최대 한 명만 배정할 수 있다. 1번의 경우 실험실 A 또는 실험실 B에 배정할 수 있고 동시에 두 곳에 배정할 수 없다. 따라서, 이 예시의 경우 최대 두 명의 보조 조교를 배치할 수 있다.
입력으로 n, nA, nB, nC 와 각 강당의 보조 조교를 희망하는 사람들의 목록이 주어졌을 때, 최대한 많은 사람을 보조 조교로 배치하려면 어떻게 해야하는지 구해보자.
첫 줄에 입력으로 들어오는 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫째 줄에는 n이 주어지고, 그 다음 줄에는 nA nB nC가 공백으로 구분되어 주어진다.
다음 세 줄에 걸쳐서 각 줄에 실험실에 지원한 사람의 목록이 주어진다. 첫째 줄에는 실험실 A에 지원한 사람의 수 mA가 주어지고, 이어 공백으로 구분된 mA명의 사람의 번호가 주어진다. 다음 줄에는 실험실 B에 지원한 사람의 수 mB가 주어지고 이어 공백으로 구분된 mB명의 사람의 번호가 주어진다. 다음 줄에는 실험실 C에 지원한 사람의 수 mC와 공백으로 구분된 mC명의 사람의 번호가 주어진다.
사람의 번호는 1보다 크거나 같고, n보다 작거나 같은 자연수이다. 지원자 목록에 같은 사람이 두 번 이상 주어지는 경우는 없다.
각각의 테스트 케이스마다 첫째 줄에 보조 조교로 배정된 사람의 수를 출력한다.
만약 배정된 사람의 수가 x라면 다음 x줄에 걸쳐서, 각 줄에 사람의 번호와 실험실 이름(A, B, C 중 하나)을 공백으로 구분해서 출력한다.
다양한 방법이 존재하는 경우, 최대한 많은 보조 조교를 배정하는 방법 중 아무 것을 출력해도 된다.
3 3 1 1 1 1 1 1 1 2 2 3 4 1 1 1 1 1 1 1 2 2 3 5 1 1 2 1 1 1 5 4 1 2 3 5
2 1 A 2 C 2 2 C 1 B 4 1 A 2 C 5 B 3 C
테스트 케이스 1: 문제에서 다룬 예시에서 4번만 없는 경우이다.
테스트 케이스 2: 문제에서 다룬 예시이다.
테스트 케이스 3: 실험실 C가 인기가 많지만, 1번과 5번은 다른 실험실에도 지원했기 때문에, 이 둘을 다른 실험실에 배정 해야 최대한 많은 보조 조교를 배정할 수 있다. 테스트 케이스 2와 마찬가지로 4번은 실험실 어느 곳도 지원하지 않았다.