31074번 - 싱글 플레이어 게임 점수다국어인터랙티브
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 10 초 | 1024 MB | 395 | 32 | 25 | 12.887% |
문제
이 문제는 인터랙티브 문제이다.
숨겨진 수열 $S$가 있다. 당신은 이 수열 $S$에 관한 정보를 알아내야 한다. 수열 $S$의 길이는 $N$이고, 아래의 조건에 모두 맞는다.
- $S$의 모든 원소는 $1$, $2$, $3$, $4$ 중 하나이다.
- $S_1=1$이다.
- $S_i=1$이라면, $S_{i+1}=1$ 또는 $S_{i+1}=2$이다. $(1\le i<N)$
- $S_i=2$이라면, $S_{i+1}=2$ 또는 $S_{i+1}=3$이다. $(1\le i<N)$
- $S_i=3$이라면, $S_{i+1}=3$ 또는 $S_{i+1}=4$이다. $(1\le i<N)$
- $S_i=4$이라면, $S_{i+1}=4$ 또는 $S_{i+1}=1$이다. $(1\le i<N)$
당신은 다음과 같은 두 가지 질문을 할 수 있다.
count l r: $[l,r]$ 구간 내에 있는 $1$, $2$, $3$, $4$의 개수를 오름차순으로 정렬한 수열을 질문한다.diff l r: $l\le i<r$이고 $S_i\neq S_{i+1}$인 $i$의 개수를 질문한다.
이때, $S$에 $1$, $2$, $3$, $4$가 각각 몇 개씩 있는지 알아내어라.
인터랙션
첫 줄에는 테스트 케이스의 수 $T$가 주어진다.
각 테스트 케이스의 시작에 수열 $S$의 길이를 나타내는 정수 $N$이 입력으로 주어진다.
질문을 하기 위해서는 다음 중 하나의 형식으로 출력한 뒤 버퍼를 비워야 한다.
count l rdiff l r
만약 질문이 count라면, 입력으로 네 정수를 입력받아야 한다. 이 네 개의 정수는 구간 $[l,r]$에서 $1$, $2$, $3$, $4$의 개수를 오름차순으로 정렬한 배열이다.
만약 질문이 diff라면, 입력으로 하나의 정수를 입력받아야 한다. 이 정수는 $l\le i<r$이고 $S_i\neq S_{i+1}$인 $i$의 개수를 나타낸다.
답을 알았다면, 다음과 같은 형식으로 출력한 뒤 버퍼를 비워야 한다. 이때, c1, c2, c3, c4는 각각 수열 $S$에서 $1$, $2$, $3$, $4$의 개수와 일치해야 한다.
answer c1 c2 c3 c4
당신의 프로그램이 조건에 맞지 않는 질문을 하거나, 질문 횟수를 초과하거나, 직전의 테스트 케이스에 대해 제시한 답이 틀린 경우 질문에 대한 답, 또는 $N$의 값 대신 $-1$을 입력받게 된다. 이 경우에 당신의 프로그램은 즉시 종료해야 하고, 채점 결과는 '틀렸습니다'를 받게 된다. 만약 프로그램이 곧바로 종료하지 않는다면 예상치 못한 채점 결과를 받을 수 있다.
하나의 테스트 케이스를 해결한 뒤에도 당신의 프로그램은 곧바로 다음 테스트 케이스로 진행해야 한다. 모든 테스트 케이스를 해결한 뒤 프로그램은 즉시 종료되어야 한다.
제한
- $1\leq T\leq 100$
- $1\leq N\leq 1\ 000$
- $S_1=1$
- $1\leq S_i\leq 4$ $(2\leq i\leq N)$
- $S_i=1\implies S_{i+1}\in\{1,2\}$ $(1\leq i<N)$
- $S_i=2\implies S_{i+1}\in\{2,3\}$ $(1\leq i<N)$
- $S_i=3\implies S_{i+1}\in\{3,4\}$ $(1\leq i<N)$
- $S_i=4\implies S_{i+1}\in\{4,1\}$ $(1\leq i<N)$
- 모든 질문에서 $1\leq l\leq r\leq N$이어야 한다.
- 인터랙터는 비적응적이다. 수열 $S$는 사전에 결정되어 있고, 질문에 따라 변하지 않는다.
점수
이 문제의 점수는 각 테스트 케이스의 질문 횟수 중 최댓값 $Q_{max}$에 따라 결정된다. $\lfloor x\rfloor$은 $x$ 이하의 최대 정수이다.
- $1000<Q_{max}$ : $0$점
- $100<Q_{max}\leq 1000$ : $10$점
- $50<Q_{max}\leq 100$ : $\lfloor 50-0.4Q_{max}\rfloor$점
- $30<Q_{max}\leq 50$ : $80-Q_{max}$점
- $19<Q_{max}\leq 30$ : $\lfloor 98-1.6Q_{max}\rfloor$점
- $Q_{max}=19$ : $70$점
- $Q_{max}=18$ : $75$점
- $Q_{max}=17$ : $82$점
- $Q_{max}=16$ : $90$점
- $Q_{max}\leq 15$ : $100$점
예제 입력 1
1 2 0 0 0 0 2
예제 출력 1
diff 1 2 count 1 2 answer 2 0 0 0
위 예제의 테스트 케이스는 하나이고, 정답 수열은 $S=[1,1]$이다.
당신의 프로그램은 먼저 수열의 길이 $N$을 입력받는다. 이 테스트 케이스에서 수열 $S$의 길이는 $2$이다.
당신의 프로그램은 diff 1 2를 출력해 질문한다. $1\le i<2$이고 $S_i\neq S_{i+1}$인 $i$가 없으므로, 답으로 정수 $0$이 주어진다.
당신의 프로그램은 count 1 2를 출력해 질문한다. 수열의 구간 $[1,2]$에서 $1$, $2$, $3$, $4$의 개수는 각각 $2$개, $0$개, $0$개, $0$개이므로, 답으로 네 정수 $0$, $0$, $0$, $2$가 주어진다.
당신의 프로그램은 answer 2 0 0 0을 출력한다. 이것은 $1$, $2$, $3$, $4$의 개수가 각각 $2$개, $0$개, $0$개, $0$개라는 뜻이다. 정답을 맞혔으므로 해당 테스트 케이스가 종료된다.
주어진 예시는 입출력이 어떤 방식으로 이루어지는지 이해를 돕기 위해 의도적으로 개행 간격 등을 조절한 것이며, 실제 입출력에서는 빈 줄을 출력하지 말아야 한다.
노트
출력 버퍼를 비우는 방법은 다음과 같다.
- C:
fflush(stdout) - C++:
std::cout << std::flush - Java:
System.out.flush() - Python:
sys.stdout.flush()
이외의 언어에 대해서는 언어별 명세를 참고해야 한다.
출처
School > 서울과학고등학교 > SciOI 2023 C-2번
- 문제를 만든 사람: math_rabbit_1028
- 문제를 검수한 사람: ibm2006, nick832, physics07, utilforever
채점 및 기타 정보
- 100점 이상을 획득해야 를 받는다.
- 예제는 채점하지 않는다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호