Scientist
This question is adapted from Euler Mathematics Competition 2014 Problem 3.
Aliens have abducted n human scientists to test their intellect. They prepared (n + 1) robes numbered from 0 to n (inclusive) with numbers painted on the back of each robe. On the day of the test, a random robe will be put aside and the rest of the robes will be randomly put on the scientists. Further, the scientists will stand in line, also in random order, so that every one of them sees numbers on colleagues in front of him but not his own and not those who are after him in the line.
Then, from back to front, each scientist guesses his own number. (He must guess a number from 0 to n. If he decides to wait, commit suicide, or do anything else, then all the scientists will be killed.) Each hears all previously made guesses, but other than that, they cannot speak. They are not allowed to repeat a number that was already announced. Each person who guesses his number wrong will be (quietly) killed on spot. The ones who guess correctly will go free after the guessing is over. The rules of the test are given to them one day before the test, at which point they have a chance to agree on a strategy that will minimize the expected number of people who will die during the test. What should that strategy be?
There are 100 test cases per subtask, and your score will be based on the average number of deaths over all the test cases in the subtasks, d. To be specific, your score will be:
- 100; if d ≤ 0.6
- 0; if d ≥ 0.8 × n
- 100 × (1 − ((d − 0.6) ÷ (0.8n − 0.6))0.25); otherwise
Functions that you must implement:
Your code will be run n times in parallel; every instance is a different scientist, so you should write code from the point of view of each scientist.
Note: Do not do "using namespace std;", or place any #include in your code. Everything has been included for you.
Implement the following functions:
void init(int n,int k,int*c);
This function will be called once before anything else is called. It is for you to initialise any global variables you might need. n is the number of scientists in total; k is the position of this scientist from the front of the line (0 ≤ k < n); c is an array of length k, where c[i] is the number on the robe of the ith scientist (zero-based indexing) from the front.
void guesscalled(int k,int g);
This function will be called every time a scientist guesses his number. k is the (zero-based) index of the scientist, and g is his guess (0 ≤ g ≤ n). You can expect the function to be called exactly n − k − 1 times before guessrequest() is called, and each time, the value of k will be one less than the previous time the function is called.
int guessrequest();
This function will be called when it is your turn to guess. Just return your guess as a single integer between 0 and n inclusive. No other function will be called after this function is called.
Constraints
Subtask 1 – 20 points: 1 ≤ n ≤ 10
Subtask 2 – 30 points: 1 ≤ n ≤ 100
Subtask 3 – 50 points: 1 ≤ n ≤ 1000
Sample
There isn't any sample. Submit your (bad) code to the judge instead.
Download the attachment "scientist.cpp", and edit the code from there.