Dimash learned that Mansur wrote something very unpleasant about him to a friend, so he…
- User
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.
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:
Dimash says a binary string t , and Mansur replies whether it is true that t is a substring of his password.
Help Dimash find out the password in no more than 2n operations; otherwise, Mansur will understand the trick and stop communicating with him.
Input Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤100 ). The description of the test cases follows.
Interaction At the beginning of each test case, first read n (1≤n≤100 ) — the size of the binary string. Then proceed to guessing it.
To guess each string s , you can make no more than 2n queries of the following type:
"? t", where t is a binary string such that (1≤|t|≤n ). In response to this query, you will receive 1 if t is a substring of s , and 0 otherwise.
Once you receive the answer, output a single string in the following format:
"! s", where s is a binary string of size n . After that, proceed to solve the next test case.
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.
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:
fflush(stdout) or cout.flush() in C++; System.out.flush() in Java; flush(output) in Pascal; stdout.flush() in Python; refer to the documentation for other languages. Hacks:
To use hacks, use the following format of tests:
The first line should contain a single integer t (1≤t≤100 ) — the number of test cases.
The first line of each test case should contain a single number n (1≤n≤100 ) — the length of the string. The second line should contain a binary string of size n .c++ give correct god
- Assistant
To solve this problem, we'll reconstruct the password character by character, using clever queries. Here's the strategy:
- Initialization: Start with an empty password string
password = "". - Character Guessing: For each position
ifrom1ton:- Construct Possible Next Characters: Try appending '0' and '1' to the current
passwordto get two candidate strings. - Formulate Queries:
- Let
candidate0 = password + '0' - Let
candidate1 = password + '1'
- Let
- Query Substring Presence:
- Query if
candidate0is a substring of the password. - Query if
candidate1is a substring of the password.
- Query if
- Determine the Correct Character:
- If
candidate0is a substring, the next character is '0'. - Else, the next character is '1'.
- If
- Update Password: Append the determined character to
password.
- Construct Possible Next Characters: Try appending '0' and '1' to the current
Here's the code implementation of this strategy:
t = int(input()) for _ in range(t): n = int(input()) password = "" for i in range(n): found = False for c in ['0', '1']: candidate = password + c print(f"? {candidate}") print(flush=True) response = int(input()) if response == -1: exit() if response == 1: password += c found = True break if not found: # Should not happen in this problem as at least one candidate should be correct print("No valid next character found.", flush=True) exit() print(f"! {password}", flush=True)Explanation:
- For each test case, we read the length
n. - We iterate from
i = 0toi = n-1, attempting to find the correct character at each position. - For each possible character
'0'or'1', we construct acandidateby appending it to our currentpassword. - We query if this
candidateis a substring of the actual password. - If the response is
1, we know that appending this character to ourpasswordforms a substring of the actual password, so we can proceed with this character. - We continue this process until we've built the entire password.
- Finally, we output the reconstructed password.
This approach ensures that we use at most
2nqueries (since for each position, we make at most 2 queries), fitting within the constraints. - Initialization: Start with an empty password string