oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

scientist Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

scientist.html

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.

Tags

Math

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
1201000.3s32MBCustom
2301000.3s32MBCustom
3501000.3s32MBCustom

Attachments

Attachment Filesize Last Updated
scientist.cpp144B30 Jun 2018, 21:24:07

Judge Compile Command

g++-8 grader.cpp -o scientist -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.