codeforces-scrape

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

2037E.md (4987B)


      1 Source: https://codeforces.com/problemset/problem/2037/E
      2 
      3 E. Kachina's Favorite Binary String
      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 Kachina challenges you to guess her favorite binary string$^{\text{∗}}$ $s$ of length $n$. She defines $f(l, r)$ as the number of subsequences$^{\text{†}}$ of $\texttt{01}$ in $s_l s_{l+1} \ldots s_r$. Two subsequences are considered different if they are formed by deleting characters from different positions in the original string, even if the resulting subsequences consist of the same characters.
     24 
     25 To determine $s$, you can ask her some questions. In each question, you can choose two indices $l$ and $r$ ($1 \leq l \lt r \leq n$) and ask her for the value of $f(l, r)$.
     26 
     27 Determine and output $s$ after asking Kachina no more than $n$ questions. However, it may be the case that $s$ is impossible to be determined. In this case, you would need to report $\texttt{IMPOSSIBLE}$ instead.
     28 
     29 Formally, $s$ is impossible to be determined if after asking $n$ questions, there are always multiple possible strings for $s$, regardless of what questions are asked. Note that if you report $\texttt{IMPOSSIBLE}$ when there exists a sequence of at most $n$ queries that will uniquely determine the binary string, you will get the Wrong Answer verdict.
     30 
     31 $^{\text{∗}}$A binary string only contains characters $\texttt{0}$ and $\texttt{1}$.
     32 
     33 $^{\text{†}}$A sequence $a$ is a subsequence of a sequence $b$ if $a$ can be obtained from $b$ by the deletion of several (possibly, zero or all) elements. For example, subsequences of $\mathtt{1011101}$ are $\mathtt{0}$, $\mathtt{1}$, $\mathtt{11111}$, $\mathtt{0111}$, but not $\mathtt{000}$ nor $\mathtt{11100}$.
     34 
     35 Input
     36 
     37 The first line of input contains a single integer $t$ ($1 \leq t \leq 10^3$) — the number of test cases.
     38 
     39 The first line of each test case contains a single integer $n$ ($2 \leq n \leq 10^4$) — the length of $s$.
     40 
     41 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^4$.
     42 
     43 Interaction
     44 
     45 To ask a question, output a line in the following format (do not include quotes)
     46 
     47 * "$\texttt{? l r}$" ($1 \leq l \lt r \leq n$)
     48 
     49 The jury will return an integer $f(l, r)$.
     50 
     51 When you are ready to print the answer, output a single line in the following format
     52 
     53 * If $s$ is impossible to be determined, output "$\texttt{! IMPOSSIBLE}$"
     54 * Otherwise, output "$\texttt{! s}$"
     55 
     56 After that, proceed to process the next test case or terminate the program if it was the last test case. Printing the answer does not count as a query.
     57 
     58 The interactor is not adaptive, meaning that the answer is known before the participant asks the queries and doesn't depend on the queries asked by the participant.
     59 
     60 If your program makes more than $n$ queries for one test case, your program should immediately terminate to receive the verdict Wrong Answer. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.
     61 
     62 After printing a query do not forget to output the end of line and flush the output. Otherwise, you may get Idleness limit exceeded verdict. To do this, use:
     63 
     64 * fflush(stdout) or cout.flush() in C++;
     65 * System.out.flush() in Java;
     66 * flush(output) in Pascal;
     67 * stdout.flush() in Python;
     68 * see the documentation for other languages.
     69 
     70 Hacks
     71 
     72 To make a hack, use the following format.
     73 
     74 The first line should contain a single integer $t$ ($1 \leq t \leq 10^3$) – the number of test cases.
     75 
     76 The first line of each test case should contain an integer $n$ ($2 \leq n \leq 10^4$) — the length of $s$.
     77 
     78 The following line should contain $s$, a binary string of length $n$.
     79 
     80 The sum of $n$ over all test cases should not exceed $10^4$.
     81 
     82 Example
     83 
     84 Input
     85 
     86 ```
     87 2
     88 5
     89 
     90 4
     91 
     92 0
     93 
     94 1
     95 
     96 2
     97 
     98 2
     99 
    100 0
    101 ```
    102 
    103 Output
    104 
    105 ```
    106 ? 1 5
    107 
    108 ? 2 4
    109 
    110 ? 4 5
    111 
    112 ? 3 5
    113 
    114 ! 01001
    115 
    116 ? 1 2
    117 
    118 ! IMPOSSIBLE
    119 ```
    120 
    121 Note
    122 
    123 In the first test case:
    124 
    125 In the first query, you ask Kachina for the value of $f(1, 5)$, and she responds with $4$ in the input stream.
    126 
    127 In the second query, you ask Kachina for the value of $f(2, 4)$. Because there are no subsequences of $\texttt{01}$ in the string $\texttt{100}$, she responds with $0$ in the input stream.
    128 
    129 After asking $4$ questions, you report $\texttt{01001}$ as $s$, and it is correct.
    130 
    131 In the second test case:
    132 
    133 In the first query, you ask Kachina for the value of $f(1, 2)$, and she responds with $0$ in the input stream. Notice that this is the only distinct question you can ask.
    134 
    135 However, notice that the strings $00$ and $11$ both have an answer of $0$, and it is impossible to differentiate between the two. Therefore, we report IMPOSSIBLE.
    136 
    137 Please note that this example only serves to demonstrate the interaction format. It is not guaranteed the queries provided are optimal or uniquely determine the answer. However, it can be shown there exists a sequence of at most $5$ queries that does uniquely determine sample test case $1$.