codeforces-scrape

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

2013C.md (2986B)


      1 Source: https://codeforces.com/problemset/problem/2013/C
      2 
      3 C. Password Cracking
      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 Dimash learned that Mansur wrote something very unpleasant about him to a friend, so he decided to find out his password at all costs and discover what exactly he wrote.
     22 
     23 Believing in the strength of his password, Mansur stated that his password — is a binary string of length $n$. He is also ready to answer Dimash's questions of the following type:
     24 
     25 Dimash says a binary string $t$, and Mansur replies whether it is true that $t$ is a substring of his password.
     26 
     27 Help Dimash find out the password in no more than $2n$ operations; otherwise, Mansur will understand the trick and stop communicating with him.
     28 
     29 Input
     30 
     31 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). The description of the test cases follows.
     32 
     33 Interaction
     34 
     35 At the beginning of each test case, first read $n$ ($1 \le n \le 100$) — the size of the binary string. Then proceed to guessing it.
     36 
     37 To guess each string $s$, you can make no more than $2n$ queries of the following type:
     38 
     39 * "? t", where $t$ is a binary string such that ($1 \le |t| \le n$).
     40 
     41 In response to this query, you will receive $1$ if $t$ is a substring of $s$, and $0$ otherwise.
     42 
     43 Once you receive the answer, output a single string in the following format:
     44 
     45 * "! s", where $s$ is a binary string of size $n$.
     46 
     47 After that, proceed to solve the next test case.
     48 
     49 If you make an incorrect attempt or exceed the limit of $2n$ attempts, you will receive $-1$ instead of an answer and get the verdict Wrong answer. In this case, your program should terminate immediately to avoid undefined verdicts.
     50 
     51 After outputting the queries, do not forget to output a newline character and flush the output buffer. Otherwise, you will receive the verdict Solution "hung". To flush the buffer, use:
     52 
     53 * fflush(stdout) or cout.flush() in C++;
     54 * System.out.flush() in Java;
     55 * flush(output) in Pascal;
     56 * stdout.flush() in Python;
     57 * refer to the documentation for other languages.
     58 
     59 Hacks:
     60 
     61 To use hacks, use the following format of tests:
     62 
     63 The first line should contain a single integer $t$ ($1\le t\le 100$) — the number of test cases.
     64 
     65 The first line of each test case should contain a single number $n$ ($1 \le n \le 100$) — the length of the string. The second line should contain a binary string of size $n$.
     66 
     67 Example
     68 
     69 Input
     70 
     71 ```
     72 4
     73 3
     74 
     75 0
     76 
     77 0
     78 
     79 1
     80 
     81 4
     82 
     83 4
     84 
     85 2
     86 ```
     87 
     88 Output
     89 
     90 ```
     91 ? 00
     92 
     93 ? 000
     94 
     95 ? 010
     96 
     97 ! 010
     98 
     99 ! 1100
    100 
    101 ! 0110
    102 
    103 ! 10
    104 ```
    105 
    106 Note
    107 
    108 In the first example, the string $010$ is given. Therefore, the answers to the queries are as follows:
    109 
    110 "? 00" $00$ is not a substring of $010$, so the answer is $0$.
    111 
    112 "? 000" $000$ is not a substring, so the answer is $0$.
    113 
    114 "? 010" $010$ is a substring, so the answer is $1$.
    115 
    116 In the second example, the string is $1100$, in the third $0110$, and in the fourth $10$.