codeforces-scrape

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

2209C.md (3532B)


      1 Source: https://codeforces.com/problemset/problem/2209/C
      2 
      3 C. Find the Zero
      4 
      5 time limit per test
      6 
      7 2 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 You are given an integer $n$. There is a hidden array $a$ of length $2n$. Each integer from $1$ to $n$ appears exactly once in $a$. The rest of the elements are all $0$.
     24 
     25 You can make the following type of query:
     26 
     27 * Choose two integers $i$ and $j$ ($1 \le i,j \le 2n$, $i \ne j$). The judge will respond with $1$ if $a_i=a_j$, and will respond with $0$ otherwise.
     28 
     29 Find any integer $k$ ($1 \le k \le 2n$) such that $a_k=0$ in no more than $n+1$ queries. Note that the interactor is adaptive, which means that the hidden array $a$ may change depending on your queries but will not contradict previous queries.
     30 
     31 Input
     32 
     33 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^3$). The description of the test cases follows.
     34 
     35 The first line of each test case contains an integer $n$ ($2 \le n \le 10^4$). The length of the hidden array $a$ will be $2n$.
     36 
     37 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^4$.
     38 
     39 Interaction
     40 
     41 To make a query, output a line in the following format:
     42 
     43 * $\texttt{?}\;i\;j$ ($1 \le i,j \le 2n$, $i \ne j$)
     44 
     45 As a response to the query, you will get:
     46 
     47 * $1$ if $a_i=a_j$;
     48 * $0$ if $a_i \ne a_j$;
     49 * $-1$ if you made an invalid query or if you exceed the limit of $n+1$ queries.
     50 
     51 To report the answer, output a line in the following format:
     52 
     53 * $\texttt{!}\;k$ ($1 \le k \le 2n$)
     54 
     55 After this, proceed to the next test case or terminate if this is the last test case.
     56 
     57 Note that reporting the answer does not count towards the $n+1$ queries.
     58 
     59 The interactor is adaptive. This means that the hidden array $a$ may change depending on your queries but will not contradict previous queries.
     60 
     61 After printing each query do not forget to output the end of line and flush$^{\text{∗}}$ the output. Otherwise, you will get Idleness limit exceeded verdict. If, at any interaction step, you read $-1$ instead of valid data, your solution must exit immediately. This means that your solution will receive Wrong answer because of an invalid query or any other mistake. Failing to exit can result in an arbitrary verdict because your solution will continue to read from a closed stream.
     62 
     63 For this problem, hacks are disabled.
     64 
     65 $^{\text{∗}}$To flush, use:
     66 
     67 * fflush(stdout) or cout.flush() in C++;
     68 * sys.stdout.flush() in Python;
     69 * see the documentation for other languages.
     70 
     71 Example
     72 
     73 Input
     74 
     75 ```
     76 2
     77 2
     78 
     79 0
     80 
     81 1
     82 
     83 3
     84 
     85 1
     86 
     87 0
     88 
     89 0
     90 ```
     91 
     92 Output
     93 
     94 ```
     95 ? 1 2
     96 
     97 ? 3 1
     98 
     99 ! 3
    100 
    101 ? 5 6
    102 
    103 ? 2 4
    104 
    105 ? 1 3
    106 
    107 ! 6
    108 ```
    109 
    110 Note
    111 
    112 In the first example test case, the hidden array $a$ is $[0,1,0,2]$:
    113 
    114 * In the first query, $(i,j)=(1,2)$. Since $a_1=0$, $a_2=1$, $a_1 \ne a_2$, the judge responds with $0$.
    115 * In the second query, $(i,j)=(3,1)$. Since $a_3=0$, $a_1=0$, $a_3 = a_1$, the judge responds with $1$.
    116 * The program reports $k=3$ as an answer. Since $a_3=0$, the answer is correct.
    117 
    118 In the second example test case, the hidden array $a$ is $[3,2,0,1,0,0]$:
    119 
    120 * In the first query, $(i,j)=(5,6)$. Since $a_5=0$, $a_6=0$, $a_5 = a_6$, the judge responds with $1$.
    121 * In the second query, $(i,j)=(2,4)$. Since $a_2=2$, $a_4=1$, $a_2 \ne a_4$, the judge responds with $0$.
    122 * In the third query, $(i,j)=(1,3)$. Since $a_1=3$, $a_3=0$, $a_1 \ne a_3$, the judge responds with $0$.
    123 * The program reports $k=6$ as an answer. Since $a_6=0$, the answer is correct.