미디언
시간 제한2초메모리 제한512 MB
서로 다른 네 직원을 골라 물으면 가운데 두 급여의 평균을 돌려주는 질의를 1000번 이하로 사용해, 답으로부터 유일하게 결정되는 모든 급여를 찾아낸다.
문제
어떤 회사들은 노조 간부들이 직원들이 얼마나 저임금을 받는지 알지 못하게 하고, 임금 인상과 보너스에 대한 지루한 협상을 피하기 위해 직원들의 급여를 비밀로 유지한다. 하지만 때때로 회사는 통계와 마케팅 목적으로 특정 정보를 공개하기도 한다.
한 회사가 다음과 같은 질문에 답할 용의가 있다. "직원 A, B, C, D의 미디언 급여는 얼마인가?" 네 수의 미디언은 두 중앙값의 산술 평균으로 정의된다. 더 정확히 말하면, 수열 a, b, c, d의 미디언은 먼저 수열을 정렬한 다음 정렬된 수열의 두 번째와 세 번째 원소를 x, y라 할 때 (x+y)/2를 계산하여 얻는다. 당신의 목표는 이러한 형태의 질문을 여러 번 하여 정확한 급여를 알아내는 것이다. 일부 직원의 급여는 모든 가능한 질문을 하더라도 절대 알아낼 수 없다는 점에 유의하라(예를 들어, 가장 낮은 급여를 받는 직원의 급여).
회사에는 1부터 N까지의 정수로 표시된 N (4 ≤ N ≤ 100)명의 직원이 있다. 각 직원의 급여는 100 000 이하의 짝수 양의 정수이며, 두 직원이 같은 급여를 받는 경우는 없다.
당신에게는 Meandian 함수를 구현한 라이브러리가 주어진다. 서로 다른 네 정수 A, B, C, D (1 ≤ A, B, C, D ≤ N)가 주어지면, 이 함수는 직원 A, B, C, D의 급여의 미디언을 반환한다.
라이브러리에 접근할 수 있을 때, 절대 알아낼 수 없는 급여를 제외한 모든 급여의 정확한 값을 찾는 프로그램을 작성하라. 프로그램은 최대 1000번의 질문을 할 수 있다.