wizardrabbit   3년 전

* 본 지문은 20462번 문제를 번역한 것입니다. 의역이 있을 수 있으며, 지문을 깔끔하게 작성할 목적으로 지문의 내용을 수정하거나 재작성했을 수도 있습니다.

문제

이 문제는 인터랙티브 문제이다.

괄호 문자열을 추측하는 프로그램을 작성해 보자.

괄호 문자열이란 아래와 같이 정의한다:

● () 는 괄호 문자열이다.

● $A$ 가 괄호 문자열이라면, ($A$) 또한 괄호 문자열이다.

● $A$, $B$ 가 괄호 문자열이라면, $AB$ 또한 괄호 문자열이다.

● 위의 경우에 해당되지 않을 경우에는 괄호 문자열이 아니다.

프로토콜

맨 처음에, 채점 프로그램은 자연수 $N$ 을 표준 입력을 통해 제공한다. $N$ 은 당신이 추측해야 할 괄호 문자열의 길이를 의미한다.

이제 채점 프로그램이 생각하고 있는 괄호 문자열을 추측하여 맞춰야 한다. 괄호 문자열을 추측하기 위해 아래와 같은 질문을 최대 $K$ 번까지 할 수 있다:

● $?$ $start$ $end$ : $start$ 번째 문자부터 $end$ 번째 문자까지 이어서 만든 문자열은 괄호 문자열인가?

각 질문에 대해, 채점 프로그램은 아래와 같이 표준 입력을 통해 답변한다:

● $start$ 번째 문자부터 $end$ 번째 문자까지 이어서 만든 문자열이 괄호 문자열이면 "Yes", 아니면 "No" (따옴표는 제외한다)

만약 채점 프로그램이 생각하고 있는 괄호 문자열을 추측하였다면, 아래와 같이 추측한 괄호 문자열을 출력할 수 있다:

● $!$ $string$ : $string$ 이 채점 프로그램이 생각한 괄호 문자열이다.

추측한 괄호 문자열을 출력한 이후, 프로그램은 반드시 종료되어야 한다.

서브태스크

가장 어려운 서브태스크만 적고자 한다.

● $2 \le N \le 50 000$

● $K = 100$ $000$

댓글을 작성하려면 로그인해야 합니다.