4M 주식회사
면접 대비시간 제한20초메모리 제한1024 MB
최솟값, 최댓값, 평균, 중앙값이 주어졌을 때 이를 만족하는 양의 정수 수열의 최소 길이를 구하고, 불가능하면 IMPOSSIBLE을 출력한다.
문제
4M 주식회사가 당신을 고용해 부서를 편성하고 인원을 배정하려 한다. 부서는 적어도 하나 만들어야 하고, 각 부서에는 양의 정수 명의 직원이 배정된다. 그런데 일이 쉽지 않다. 상사가 넷이고, 각자 다른 지시를 내렸다.
- 직원이 가장 적은 부서의 직원 수는 정확히 MINIMUM이어야 한다.
- 직원이 가장 많은 부서의 직원 수는 정확히 MAXIMUM이어야 한다.
- 모든 부서의 직원 수 평균은 정확히 MEAN이어야 한다.
- 모든 부서의 직원 수 중앙값은 정확히 MEDIAN이어야 한다. 중앙값이란 목록을 감소하지 않는 순서로 정렬했을 때 가운데에 오는 값(목록 길이가 홀수인 경우) 또는 가운데 두 값의 평균(목록 길이가 짝수인 경우)이다.
또한 효율을 위해 부서를 너무 많이 만드는 것은 좋지 않다. 상사들의 요구를 모두 만족시키는 것이 가능하다면, 만들 수 있는 부서 수의 최솟값은 얼마인가?
입력
입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어지며, 각 테스트 케이스는 네 정수 MINIMUM, MAXIMUM, MEAN, MEDIAN으로 이루어진다.
출력
각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 가능한 부서 수의 최솟값 또는 네 상사의 요구를 모두 만족시키는 것이 불가능할 경우 IMPOSSIBLE이다.
제한
- 1 ≤ T ≤ 100.
힌트
예제 1은 최댓값이 최솟값보다 작을 수 없으므로 IMPOSSIBLE이다.
예제 2는 평균과 중앙값이 최댓값보다 클 수 없으므로 IMPOSSIBLE이다.
예제 3에서는 직원 2명인 부서 하나를 만들면 된다. 이는 네 상사의 요구를 모두 만족한다. 직원이 가장 적은 부서의 직원 수가 정확히 2이고, 직원이 가장 많은 부서의 직원 수도 정확히 2이며, 평균과 중앙값도 모두 2이다.
예제 4에서는 직원 3명인 부서 하나와 직원 7명인 부서 하나를 만들면 된다. 직원 5명인 부서 하나만 만드는 것으로는 충분하지 않다. 그 경우 직원이 가장 적은 부서의 직원 수가 정확히 3이 아니고, 직원이 가장 많은 부서의 직원 수도 정확히 7이 아니기 때문이다.
예제 5에서는 직원 1명인 부서 하나와 직원 4명인 부서 두 개를 만들면 된다.