육아 파트너링 리턴즈
면접 대비시간 제한20초메모리 제한1024 MB
각 활동을 두 사람 중 한 명에게 배정해 같은 사람이 겹치는 활동을 맡지 않게 합니다. 그럴 수 없으면 IMPOSSIBLE을 출력합니다.
문제
카메론과 제이미의 아이가 이제 거의 세 살이 되었다. 아이는 전보다 더 자립했지만, 아이 활동과 집안일의 일정을 짜는 일은 여전히 이 부부에게 어려운 과제다.
카메론과 제이미에게는 하루 동안 처리해야 할 활동 N개의 목록이 있다. 각 활동은 하루 중 정해진 구간에서 진행된다. 두 사람은 각 활동을 둘 중 한 명에게 배정해야 하며, 누구도 서로 겹치는 활동 두 개를 맡아서는 안 된다. 시각 t에 끝나는 활동과 시각 t에 시작하는 다른 활동은 겹치는 것으로 보지 않는다.
예를 들어, 제이미와 카메론이 활동 3개를 나눠 맡는다고 하자. 첫 번째 활동은 18:00부터 20:00까지, 두 번째는 19:00부터 21:00까지, 세 번째는 22:00부터 23:00까지 진행된다. 제이미가 19:00부터 21:00까지의 활동을 맡고 카메론이 나머지 두 개를 맡을 수 있다. 반대로 카메론이 18:00부터 20:00까지의 활동을 맡고 제이미가 나머지 두 개를 맡아도 유효한 일정이다. 처음 두 활동은 19:00부터 20:00까지 겹치므로, 두 활동을 같은 사람에게 배정할 수는 없다.
각 활동의 시작 시각과 종료 시각이 주어졌을 때, 같은 사람이 겹치는 활동을 맡지 않는 일정을 하나 찾거나, 그런 일정이 불가능하다고 답하라.
입력
첫 줄에 테스트 케이스의 개수 T가 주어진다. 이어서 T개의 테스트 케이스가 나온다. 각 테스트 케이스는 배정할 활동의 개수 N을 적은 줄로 시작한다. 그 뒤로 N개의 줄이 이어진다. 이 중 i번째 줄(1부터 셈)에는 정수 Si와 Ei가 주어진다. i번째 활동은 자정으로부터 정확히 Si분 뒤에 시작하여 정확히 Ei분 뒤에 끝난다.
출력
각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이다. 위 규칙을 따르는 유효한 일정이 없으면 y는 IMPOSSIBLE이다. 그렇지 않으면 정확히 N글자로 된 문자열을 출력한다. y의 i번째 글자는 i번째 활동을 카메론에게 배정하면 C, 제이미에게 배정하면 J이다.
해가 여러 개라면 그중 아무거나 하나를 출력해도 된다.
제한
- 1 ≤ T ≤ 100.
- 0 ≤ Si < Ei ≤ 24 × 60.
힌트
예제 1번은 문제 설명에서 든 경우다. 위에서 말했듯이 JCJ나 JCC 같은 다른 유효한 답도 있다.
예제 2번에서는 활동 3개가 모두 서로 겹친다. 세 활동을 모두 배정하면 누군가는 겹치는 활동을 최소 두 개 맡게 되므로 유효한 일정이 없다.
예제 3번에서는 카메론이 100분에 활동 하나를 끝내고 곧바로 다른 활동을 시작하는 점에 주목하라.
예제 4번에서는 어떤 일정이든 유효하다. 특히 한 사람이 모든 활동을 맡아도 괜찮다.