codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1867C.md (3830B)


      1 Source: https://codeforces.com/problemset/problem/1867/C
      2 
      3 C. Salyg1n and the MEX Game
      4 
      5 time limit per test
      6 
      7 3 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 This is an interactive problem!
     22 
     23 salyg1n gave Alice a set $S$ of $n$ distinct integers $s_1, s_2, \ldots, s_n$ ($0 \leq s_i \leq 10^9$). Alice decided to play a game with this set against Bob. The rules of the game are as follows:
     24 
     25 * Players take turns, with Alice going first.
     26 * In one move, Alice adds one number $x$ ($0 \leq x \leq 10^9$) to the set $S$. The set $S$ must not contain the number $x$ at the time of the move.
     27 * In one move, Bob removes one number $y$ from the set $S$. The set $S$ must contain the number $y$ at the time of the move. Additionally, the number $y$ must be strictly smaller than the last number added by Alice.
     28 * The game ends when Bob cannot make a move or after $2 \cdot n + 1$ moves (in which case Alice's move will be the last one).
     29 * The result of the game is $\operatorname{MEX}\dagger(S)$ ($S$ at the end of the game).
     30 * Alice aims to maximize the result, while Bob aims to minimize it.
     31 
     32 Let $R$ be the result when both players play optimally. In this problem, you play as Alice against the jury program playing as Bob. Your task is to implement a strategy for Alice such that the result of the game is always at least $R$.
     33 
     34 $\dagger$ $\operatorname{MEX}$ of a set of integers $c_1, c_2, \ldots, c_k$ is defined as the smallest non-negative integer $x$ which does not occur in the set $c$. For example, $\operatorname{MEX}(\{0, 1, 2, 4\})$ $=$ $3$.
     35 
     36 Input
     37 
     38 The first line contains an integer $t$ ($1 \leq t \leq 10^5$) - the number of test cases.
     39 
     40 Interaction
     41 
     42 The interaction between your program and the jury program begins with reading an integer $n$ ($1 \leq n \leq 10^5$) - the size of the set $S$ before the start of the game.
     43 
     44 Then, read one line - $n$ distinct integers $s_i$ $(0 \leq s_1 \lt s_2 \lt \ldots \lt s_n \leq 10^9)$ - the set $S$ given to Alice.
     45 
     46 To make a move, output an integer $x$ ($0 \leq x \leq 10^9$) - the number you want to add to the set $S$. $S$ must not contain $x$ at the time of the move. Then, read one integer $y$ $(-2 \leq y \leq 10^9)$.
     47 
     48 * If $0 \leq y \leq 10^9$ - Bob removes the number $y$ from the set $S$. It's your turn!
     49 * If $y$ $=$ $-1$ - the game is over. After this, proceed to handle the next test case or terminate the program if it was the last test case.
     50 * Otherwise, $y$ $=$ $-2$. This means that you made an invalid query. Your program should immediately terminate to receive the verdict Wrong Answer. Otherwise, it may receive any other verdict.
     51 
     52 After printing a query do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:
     53 
     54 * fflush(stdout) or cout.flush() in C++;
     55 * System.out.flush() in Java;
     56 * flush(output) in Pascal;
     57 * stdout.flush() in Python;
     58 * see the documentation for other languages.
     59 
     60 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
     61 
     62 Do not attempt to hack this problem.
     63 
     64 Example
     65 
     66 Input
     67 
     68 ```
     69 3
     70 5
     71 1 2 3 5 7
     72 
     73 7
     74 
     75 5
     76 
     77 -1
     78 
     79 3
     80 0 1 2
     81 
     82 0
     83 
     84 -1
     85 
     86 3
     87 5 7 57
     88 
     89 -1
     90 ```
     91 
     92 Output
     93 
     94 ```
     95 8
     96 
     97 57
     98 
     99 0
    100 
    101 3
    102 
    103 0
    104 
    105 0
    106 ```
    107 
    108 Note
    109 
    110 In the first test case, the set $S$ changed as follows:
    111 
    112 {$1, 2, 3, 5, 7$} $\to$ {$1, 2, 3, 5, 7, 8$} $\to$ {$1, 2, 3, 5, 8$} $\to$ {$1, 2, 3, 5, 8, 57$} $\to$ {$1, 2, 3, 8, 57$} $\to$ {$0, 1, 2, 3, 8, 57$}. In the end of the game, $\operatorname{MEX}(S) = 4$, $R = 4$.
    113 
    114 In the second test case, the set $S$ changed as follows:
    115 
    116 {$0, 1, 2$} $\to$ {$0, 1, 2, 3$} $\to$ {$1, 2, 3$} $\to$ {$0, 1, 2, 3$}. In the end of the game, $\operatorname{MEX}(S) = 4$, $R = 4$.
    117 
    118 In the third test case, the set $S$ changed as follows:
    119 
    120 {$5, 7, 57$} $\to$ {$0, 5, 7, 57$}. In the end of the game, $\operatorname{MEX}(S) = 1$, $R = 1$.