높은 건물
면접 대비시간 제한20초메모리 제한1024 MB
N개 건물의 높이를 정해 왼쪽에서 A개, 오른쪽에서 B개, 양쪽에서 C개가 보이게 만들고, 불가능하면 IMPOSSIBLE을 출력한다.
문제
어느 나라에 Google의 사무실 단지가 있고, 이 단지는 일렬로 늘어선 N개의 사무용 건물로 이루어져 있다. 건물은 왼쪽에서 오른쪽으로 1부터 N까지 번호가 붙어 있다. 각 건물의 높이를 미터 단위로 나타내면 1 이상 N 이하의 정수다.
Andre와 Sule은 이 단지에서 일하는 Google 직원이다. 두 사람은 점심시간에 자신들이 일하는 단지의 스카이라인을 보고 싶었다. 그래서 Andre는 단지의 가장 왼쪽 지점(건물 1의 왼쪽)으로 가서 단지의 가장 오른쪽 지점(건물 N의 오른쪽)을 바라보았고, Sule은 단지의 가장 오른쪽 지점으로 가서 단지의 가장 왼쪽 지점을 바라보았다.
Andre에게 건물 가 보인다는 것은 의 왼쪽에 보다 더 높은 건물이 없다는 것과 동치이다. 마찬가지로 Sule에게 건물 가 보인다는 것은 의 오른쪽에 보다 더 높은 건물이 없다는 것과 동치이다.
Andre는 자신에게 보이는 건물이 A개라는 사실을 알게 되었고, Sule은 자신에게 보이는 건물이 B개라는 사실을 알게 되었다. 두 사람은 다시 만나 정보를 교환한 뒤, 둘 모두에게 보이는 건물이 C개라는 사실도 알게 되었다.
두 사람은 각 건물의 높이를 궁금해한다. 이들은 참고용으로 N, A, B, C 값을 당신에게 준다. 친구인 당신은 앞 문단에서 알아낸 정보가 맞도록 각 건물의 높이를 정하는 한 가지 방법을 구성하거나, 그 정보에 맞는 높이 배치가 없음을 밝혀야 한다(즉, 두 사람 중 적어도 한 명은 잘못 알고 있었던 것이다).
입력
첫 줄에는 테스트 케이스 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 한 줄에 네 정수 N, A, B, C가 주어지는 형식이다. 이 값들은 Andre와 Sule이 알게 된 정보이다.
출력
각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y는 위 정보에 맞는 각 건물의 높이가 존재하지 않으면 IMPOSSIBLE, 존재하면 공백으로 구분된 N개의 정수이다. y의 i번째 정수는 i번째 건물의 높이(미터)이며 1 이상 N 이하여야 한다.
제한
힌트
예제 1에서 예제 출력은 Andre에게 첫 번째 건물만 보이고 Sule에게 첫 번째, 세 번째, 네 번째 건물이 보이도록 각 건물의 높이를 정한다. 따라서 Andre와 Sule 모두에게는 첫 번째 건물만 보인다. 4 3 1 2처럼 다른 올바른 답도 있다.
예제 2에서는 N = 4이고, 모든 건물이 Andre와 Sule 모두에게 보인다. 따라서 이 경우 이 되게 하는 것은 불가능하다.
예제 3에서 예제 출력은 Andre에게 첫 번째, 세 번째, 네 번째 건물이 보이고 Sule에게 세 번째, 네 번째, 다섯 번째 건물이 보이도록 각 건물의 높이를 정한다. 따라서 세 번째와 네 번째 건물이 Andre와 Sule 모두에게 보인다. 다른 올바른 답도 있다.