20405번 - Meandian 다국어언어 제한함수 구현

Some companies like to keep the salaries of their employees secret in order to prevent union leaders from knowing how underpaid the employees are and hence avoid boring negotiations about raises and bonuses. Sometimes, however, companies are happy to release certain information for statistical and marketing purposes.

One particular company is willing to answer questions of the following form: "What is the meandian salary of employees A, B, C and D?". The meandian of four numbers is defined as the arithmetic mean of the two median values. More precisely, the meandian of a sequence a, b, c, d, is obtained by first sorting the sequence and then calculating (x+y)/2 where x and y are the second and third elements in the sorted sequence. Your goal is to figure out the exact salaries by asking a number of questions of this form. Notice that the salaries of some employees can never be deduced (for example, the salary of the lowest paid employee) even if all possible questions are asked.

The company has N (4 ≤ N ≤ 100) employees marked with integers 1 to N. The salary of each employee is an even positive integer less than or equal to 100 000 and no two employees have the same salary.

You are provided with a library implementing the function Meandian. Given four distinct integers A, B, C, D (1 ≤ A, B, C, D ≤ N), this function returns the meandian of the salaries of employees A, B, C and D.

Write a program that, given access to the library, finds the exact values of all salaries, except those that can never be determined. Your program is allowed to ask at most 1000 questions.

You are given access to the library implementing the following three functions:

int Init(void); – called with no arguments. This function should be called exactly once, at the beginning of your program. It takes no arguments and returns the integer N – the number of employees in the company.

int Meandian(int,int,int,int); – this function should be called with four arguments A, B, C, D – distinct integers between 1 and N, inclusive. It returns an integer, the meandian of the salaries of employees A, B, C and D.

void Solution(const int *); – this function should be called at the end of your program. It takes as an argument an array of integers representing salaries of the corresponding employees. If the salary of a particular employee cannot be determined, the corresponding value in the array should be –1.

Note that the return array should be 0-indexed in all programming languages. This means that the salary of employee 1 should be at position 0 in the array, the salary of employee 2 at position 1 etc.

The provided sample library allows you to test your solution by entering the number N followed by N even integers on the standard input.

Following are snippets of code that do not solve the problem at all, but serve as examples of using the library in different programming languages.

#include "libmean.h"
void solve(void)
{
    int i, n;
    int arr[100];
    int foo, bar, quux;
    n = Init();
    foo = Meandian(1, 2, 3, 4);
    bar = Meandian(4, 2, 3, 1);
    quux = Meandian(n, n-1, n-2, n-3);
    for (i=1; i<=n; ++i)
        arr[i-1] = 2*i;
    arr[3] = -1;
    Solution(arr);
    return 0;
} 

Here is an example of how to enter input for your program linked with the provided sample library. The library will tell you if your solution is correct.

10
100 500 200 400 250 300 350 600 550 410

• libmean.h