| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 25 | 12 | 11 | 61.111% |
이 문제는 인터랙티브 문제이다.
시을이는 괄호괄호 행성에서 온 외계인으로, 오직 괄호 문자열을 통해서만 소통한다. 괄호 문자열은 아래와 같이 정의된 문자열이다.
S가 괄호 문자열이라면 (S)와 {S}도 괄호 문자열이다.S, T가 괄호 문자열이라면 ST도 괄호 문자열이다.이를테면 {()}, ({}){}는 모두 괄호 문자열이므로 괄호괄호 행성 언어에 존재하는 단어이지만, (){{}, {(}와 같은 문자열은 괄호 문자열이 아니므로 존재하는 단어가 아니다.
어느 날, 평범한 인간인 도윤이는 우연히 만난 시을이에게 첫눈에 반해버렸다. 하지만, 도윤이는 괄호 문자열로 ’사랑해’라는 뜻의 문자열이 무엇인지 알지 못하기 때문에 시을이에게 마음을 전할 수 없었다. 도윤이는 인터넷 검색을 통해 다음과 같은 사실을 알게 되었다.
도윤이는 $S$를 알아내기 위해 시을이에게 길이 2ドルN$의 괄호 문자열의 뜻을 물어보려고 한다. 그러나, 도윤이가 $S$가 아닌 다른 문자열의 뜻을 너무 많이 물어보면 시을이는 도윤이가 자신을 싫어한다고 오해할 수 있다. 문자열을 최대한 적은 횟수로 질문하여 $S$를 알아내자.
첫째 줄에 정수 $N$이 주어진다. (1ドル\leq N\leq 100$)
당신은 표준 출력 스트림(stdout)으로 길이 2ドルN$의 괄호 문자열 $T$를 ? T와 같이 출력하여, 문자열 $T$가 무슨 뜻인지 시을이에게 질문할 수 있다. 질문을 출력한 뒤에는 반드시 버퍼를 비워야 하며, 하나의 실행에서 최대 10000ドル$번의 질문을 할 수 있다. 만약 10000ドル$번 초과의 질문을 하게 되면 당신의 프로그램은 더 이상 실행되지 않으며, 해당 테스트케이스에 대해 틀렸습니다를 받게 된다.
질문을 한 뒤, 당신은 인터랙터에게서 정수 $x$를 입력받아 질문의 답을 알 수 있다.
’사랑해’라는 뜻의 괄호 문자열 $S$를 알아냈다면, ! S와 같이 $S$를 출력하고 프로그램을 즉시 종료해야 한다. 이때, 해당 출력은 질문으로 취급되지 않는다.
만약 ? S나 ! S가 아닌 유효하지 않은 출력을 한다면, 인터랙터는 -1을 반환한다. 이 경우에 프로그램은 즉시 종료되어야 하고, 해당 테스트케이스에 대해 채점 결과는 틀렸습니다를 받게 된다. 만약 프로그램이 곧바로 종료하지 않는다면 예상치 못한 채점 결과를 받을 수 있다.
모든 실행에 대해 10000ドル$번 이하의 질문을 통해 ’사랑해’라는 뜻의 괄호 문자열 $S$를 알아냈다면, 질문을 적게 사용할수록 높은 점수를 얻게 된다. 한 번의 실행에서 사용한 질문 수의 최댓값을 $Q$라고 할 때, $f(Q)$를 정수로 내림한 값의 점수를 얻게 된다. $f$는 아래와 같이 정의된 연속함수이다.\[f(Q) =\begin{cases}100&(Q\leq 201)\\ 301-Q&(201<Q\leq 205)\\\frac{1397}{9} -\frac{13}{45} Q&(205<Q\leq 295)\\ 365-Q&(295<Q\leq 305)\\\frac{845}{9} -\frac{1}{9} Q&(305<Q\leq 395)\\ 445-Q&(395<Q\leq 405)\\\frac{6785}{119} -\frac{5}{119} Q&(405<Q\leq 1000)\\ 15&(1000<Q\leq 10000)\\\end{cases}\]
아래 표는 각각의 경곗값에 대한 $f(Q)$의 값이다.
4 2 4 4 0
? {{}}(){}
? {()}(){}
? {{}}()()
? ({})(){}
! ({})(){}
예제는 이해를 돕기 위해 개행 간격을 의도적으로 조절한 것으로, 실제 입출력에서는 빈 줄을 입력받거나 출력하지 않아야 한다.
출력 버퍼를 비우는 방법은 다음과 같다.
fflush(stdout)std::cout << std::flushSystem.out.flush()sys.stdout.flush()이외의 언어에 대해서는 언어별 명세를 참고해야 한다.
School > 서울과학고등학교 > SciOI 2025 I번