guessinggame
EGOI Day 2 Tasks
English (ISC)

D. Guessing Game
Problem Name

Guessing GameTime Limit

4 seconds

Memory Limit

1 gigabyte

In the old town of Lund, there is a street with N houses in a row, indexed 0 to N − 1. Emma lives
in one of these houses and her friends Anna and Bertil want to ﬁgure out which one. Instead ofjust telling her friends where she lives, Emma decides to play a game with them. Before the gamestarts, Anna and Bertil only know the number of houses on the street. At this point, Anna and Bertilmay pick a positive integer K and agree on a strategy. Any communication thereafter is forbidden.
The game itself consists of two phases. In the ﬁrst phase, Emma picks an order in which to visit thehouses, such that her house is the last one to visit. She then leads Anna to the houses one by one
in this order, without telling Anna the order in advance. For each house that is not Emma's house,
Anna is allowed to write a single integer between 1 and K on the front door of the house with apiece of chalk. For the last house they visit, Emma's house, Emma writes an integer between 1 andK on the door herself.
In the second phase of the game, Bertil walks along the street from house 0 to house N − 1 andreads all the numbers written on the doors by Anna and Emma. He now wants to guess whichhouse Emma lives in. He has two chances to guess correctly and he and Anna win the game if hesucceeds. Otherwise, Emma wins the game.
Can you devise a strategy where Anna and Bertil are guaranteed to win the game? Your strategy
will be scored based on the value of K (the smaller, the better).

Implementation
This is a multi-run problem, meaning that your program will be executed multiple times. The ﬁrst
time it is run, it will implement Anna's strategy. After that it will implement Bertil's.
The ﬁrst line of the input will contain two integers, P and N , where P is either 1 or 2 (ﬁrst orsecond phase), and N is the number of houses. Except for the sample input (not used forscoring), N will always equal 100 000.
The following input depends on the phase:
guessinggame (1 of 5)

Phase 1Your program should start by outputting the number K on a single line (1 ≤ K ≤ 1 000 000).
Then, N − 1 times, it should read a line containing an index i (0 ≤ i < N ), and output a line withan integer Ai (1 ≤ Ai ≤ K), where Ai is the number Anna writes on the door of house i . Every
index i except the index of Emma's house will appear exactly once, in some order decided by thegrader.

Phase 2Your program should read a line with N integers, A0 , A1 , … , AN −1 , where Ai is the number
written on the door of house i .
Then, it should print a line with two integers, s 1 and s 2 (0 ≤ s i < N ), the guessed indices. s 1 ands2 are allowed to be equal.

Implementation Details
Note that when running your program in Phase 2, the program is restarted. This means that you
cannot save the information in some variables between the runs.
After each line you print, make sure to ﬂush standard output, or else your program might get
judged as Time Limit Exceeded. In Python, print() ﬂushes automatically. In C++, cout << endl;
also ﬂushes in addition to printing a newline; if using printf, use fflush(stdout).
The grader for this problem may be adaptive, meaning it may change its behavior depending on
the output of your program to prevent heuristic solutions from passing. It might do a trial run ofphase 1, look at your output, and then run phase 1 for real using information it extracted from theprevious run.
Your program must be deterministic, that is behave the same if run twice on the same input. If
you want to use randomness in your program, make sure to use a ﬁxed random seed. This can bedone by passing a hard-coded constant to srand (in C++) or random.seed (in Python), or, if using
C++11's random number generators, by specifying the seed when constructing the random
number generator. In particular, you can not use srand(time(NULL)) in C++. If the grader
detects that your program is not deterministic, it will be given a Wrong Answer verdict.
If the sum of the runtimes of the (up to 3) separate runs of your program exceeds the time limit,
your submission will be judged as Time Limit Exceeded.

ScoringYour solution will be tested on a number of test cases. If your solution fails on any of these test
cases (e.g. by giving wrong answers (Wrong Answer), crashing (Run-Time Error), exceeding theguessinggame (2 of 5)

time limit (Time Limit Exceeded), etc.), you will receive 0 points and the appropriate verdict.
If your program successfully ﬁnds the index of Emma's house in all test cases, you will get theverdict Accepted, and a score calculated as follows. Let Kmax be the maximum value of K used forany test case. Depending on Kmax:
Score

Kmax > 99 998

10 points

10 000 < Kmax ≤ 99 998

10 + ⌊40(1 − Kmax/105 )⌋ points

30 < Kmax ≤ 10 000

46 + ⌊31(4 − log10 (Kmax))/(4 − log10 (30))⌋ points

7 < Kmax ≤ 30

107 − Kmax points

Kmax ≤ 7

100 points

The scoring function is depicted in the ﬁgure below.

The sample test case is ignored for scoring, and your solution does not have to work for it.

Testing Tool
To facilitate the testing of your solution, we provide a simple tool that you can download. See“attachments” at the bottom of the Kattis problem page. The tool is optional to use, and you areallowed to change it. Note that the oﬃcial grader program on Kattis is diﬀerent from the testingtool.

guessinggame (3 of 5)

Example usage (with N = 4, s = 2, where s is the number written on the last house visited):
For Python programs, say solution.py (normally run as pypy3 solution.py):
python3 testing_tool.py pypy3 solution.py <<<"4 2"
For C++ programs, ﬁrst compile it (e.g. with g++-g-O2-std=gnu++17-staticsolution.cpp -o solution.out) and then run:python3 testing_tool.py ./solution.out <<<"4 2"
The testing tool will visit the houses in random order. To use a speciﬁc order, modify the testing
tool where it says “MODIFY HERE”.

Example Interaction
The sample test case is ignored for scoring, and your solution does not have to work for it.
Suppose we have N = 4 and that Emma lives in house 1. Let A be the list of numbers written on
the houses. Initially, A = [0, 0, 0, 0], where 0 means that no number is written on thecorresponding house.
In the ﬁrst run of your code:

N = 4 is given. Your solution responds with K = 3.
A2 is asked for. Your solution responds with 3. A is now [0, 0, 3, 0].
A0 is asked for. Your solution responds with 1. A is now [1, 0, 3, 0].
A3 is asked for. Your solution responds with 2. A is now [1, 0, 3, 2].
Finally, the grader sets A1 = 2, so that A = [1, 2, 3, 2] in the end. This marks the end of the ﬁrst
phase.
In the Phase 2 of your code, your solution is passed the list 1 2 3 2.
It responds with 1 3.
Since one of the guesses is the correct index of the house (1), Anna and Bertil win the game.

guessinggame (4 of 5)

grader output

your output

14
32
30
1
3
2
grader output

your output

241232
13

guessinggame (5 of 5)