[Codeforces Round 973(Div. 2)] C. Password Cracking

https://codeforces.com/contest/2013/problem/C

Codeforces Round 973(Div. 2) - C. Password Cracking

문제 유형 : 구현

제한 시간: 2초

제한 메모리: 256MB

 

문제

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 𝑛. 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 𝑡 is a substring of his password.

Help Dimash find out the password in no more than 2𝑛 operations; otherwise, Mansur will understand the trick and stop communicating with him.

 

디매시는 친구에게 만수르가 디매시에 대해 모욕적인 이야기를 적었다는 걸 알아서, 그는 패스워드를 때려맞춰서 뭐라고 썼는지 보려고 합니다.

만수르의 패스워드는 n의 길이의 바이너리 문자열 패스워드입니다.

디매시가 바이너리 문자열 t를 질의하면, 만수르는 그의 t가 비밀번호의 부분문자열인지 알려줍니다.

디매시가 2n번 이내로 찾게 도와주세요. 횟수를 넘으면, 만수르는 눈치채고 대화를 하려 하지 않을 것입니다.

 

입력

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.

 

첫 줄에 테스트 케이스 t가 주어진다.

그리고 t번의 인터렉션이 시작된다.

 

인터랙션

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 𝑠, you can make no more than 2𝑛 queries of the following type:

• "? t", where 𝑡 is a binary string such that (1≤|𝑡|≤𝑛).

In response to this query, you will receive 11if 𝑡t is a substring of 𝑠s, and 0 otherwise.

Once you receive the answer, output a single string in the following format:

• "! s", where 𝑠 is a binary string of size 𝑛.

After that, proceed to solve the next test case.

If you make an incorrect attempt or exceed the limit of 2𝑛 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.

매 번의 인터렉션마다, n이 우선 주어진다. 이는 비밀번호의 길이이다.

당신은 쿼리메시지를 출력할 수 있다.

"? t"로 t문자열이 부분문자열인지 질의할 수 있다.

그리고, 응답을 표준입력으로 받는데, 1이면 t가 s안에 있다는 뜻이다.

 

최종 답안을 선택했다면, "! s"로 문자열 s가 비밀번호라고 제출하여라.

당신 측에서 출력을 할 때 마다, 개행문자로 마무리하고 출력 스트림을 플러시 해줘야 한다.

 

 

풀이

부분문자열인지만 확인하므로, 질의에 대해 1을 반환한다고 해서 t가 s에서 0번부터 일치한다는 보장은 없다.

그래서, 양쪽 prefix쪽과 postfix쪽을 만들어보면서 쿼리를 날리는 수밖에 없다.

만약 한 쪽이 다 완성되고, 다른 쪽을 완성하는 도중 1이 틀리면, 반드시 0이 될것이다.

처음 한 방향을 만드는 쪽이라면, 0이나 1을 붙이는 걸 둘다 질의해봐야 한다. 둘다 아닐수도 있기 때문이다.

 

각 테스트케이스마다 다음을 반복한다:

 우선, 예상 비밀번호를 ""로 시작한다.

 현재 문자열의 길이가 n보다 작은동안 다음을 반복한다:

  현재 비밀번호 + "0"을 질의한다. 만약 부분문자열이 맞다면, 뒤에 "0"을 실제로 추가한다.

  아니라면, 현재 비밀번호 "1"을 질의한다. 만약 부분문자열이 맞다면, 뒤에 "1"을 실제로 추가한다.

  그것도 아니라면, 이 반복을 그만둔다. 이제 postfix부분은 완성되었다는 뜻이다.

이제, prefix부분을 만들어보자. 다시 현재 문자열의 길이가 n보다 작은동안 다음을 반복한다:

 "0" + 현재 비밀번호를 질의한다. 만약 부분문자열이 맞다면, 맨 앞에 "0"을 추가한다.

  그게 아니라면, 맨 앞에 "1"을 추가한다.

 "! (비밀번호)"를 출력하여 마친다.

 

 

코드

C++

#include <iostream>
#include <string>

using namespace std;

bool query(string pass) {
  cout << "? " << pass << "\n";
  cout.flush();
  int res;
  cin >> res;
  return res;
}

void revealPass(string pass) {
  cout << "! " << pass << "\n";
  cout.flush();
}

void solve() {
  int n;
  cin >> n;
  string pass = "";
  while(pass.size() < n) {
    if(query(pass + "0")) {
      pass += "0";
    } else if(query(pass + "1")) {
      pass += "1";
    } else break;
  }

  while(pass.size() < n) {
    if(query("0" + pass)) {
      pass = "0" + pass;
    } else {
      pass = "1" + pass;
    }
  }
  revealPass(pass);
}

int main() {

    int t;
    cin >> t;

    while (t--) {
      solve();
    }
    return 0;
}