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$.