20462번 - Программирование квадрокоптеров
* 본 지문은 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$
댓글을 작성하려면 로그인해야 합니다.
wizardrabbit 3년 전 4
* 본 지문은 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$