Description

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 \le N \le 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 \le A, B, C, D \le 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.

Library

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. 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.

10
100 500 200 400 250 300 350 600 550 410

Hint

Testing

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

The library will output a message indicating whether your solution was correct. It will also create a text file meandian.log containing details of your program's execution.

Following is a snippet of code that do not solve the problem at all, but serves as an example of using the library.

int Init();
int Meandian(int a,int b,int c,int d);
void Solution(const int * a);
int main(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;
}