싱글 플레이어 게임

시간 제한10초메모리 제한1024 MB

요약
count(구간 값 정렬)와 diff(인접 변화 수) 질문을 써서, 1..4가 한 칸씩만 오르내리는 숨은 수열에서 각 숫자의 개수를 알아낸다.
난이도

보통10점 중 7점

유형
수학, 완전 탐색, 구현, 이분 탐색
정답자
아직 제출이 없습니다

문제

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

숨겨진 수열 SS가 있다. 당신은 이 수열 SS에 관한 정보를 알아내야 한다. 수열 SS의 길이는 NN이고, 아래의 조건에 모두 맞는다.

  • SS의 모든 원소는 11, 22, 33, 44 중 하나이다.
  • S_1=1S\_1=1이다.
  • S_i=1S\_i=1이라면, S_i+1=1S\_{i+1}=1 또는 S_i+1=2S\_{i+1}=2이다. (1≤i\<N)(1\le i\<N)
  • S_i=2S\_i=2이라면, S_i+1=2S\_{i+1}=2 또는 S_i+1=3S\_{i+1}=3이다. (1≤i\<N)(1\le i\<N)
  • S_i=3S\_i=3이라면, S_i+1=3S\_{i+1}=3 또는 S_i+1=4S\_{i+1}=4이다. (1≤i\<N)(1\le i\<N)
  • S_i=4S\_i=4이라면, S_i+1=4S\_{i+1}=4 또는 S_i+1=1S\_{i+1}=1이다. (1≤i\<N)(1\le i\<N)

당신은 다음과 같은 두 가지 질문을 할 수 있다.

  • count l r: \[l,r]\[l,r] 구간 내에 있는 11, 22, 33, 44의 개수를 오름차순으로 정렬한 수열을 질문한다.
  • diff l r: l≤i\<rl\le i\<r이고 S_i≠S_i+1S\_i\neq S\_{i+1}인 ii의 개수를 질문한다.

이때, SS에 11, 22, 33, 44가 각각 몇 개씩 있는지 알아내어라.

제한

  • 1≤T≤1001\leq T\leq 100
  • 1≤N≤1 0001\leq N\leq 1\ 000
  • S_1=1S\_1=1
  • 1≤S_i≤41\leq S\_i\leq 4 (2≤i≤N)(2\leq i\leq N)
  • S_i=1  ⟹  S_i+1∈1,2S\_i=1\implies S\_{i+1}\in\\{1,2\\} (1≤i\<N)(1\leq i\<N)
  • S_i=2  ⟹  S_i+1∈2,3S\_i=2\implies S\_{i+1}\in\\{2,3\\} (1≤i\<N)(1\leq i\<N)
  • S_i=3  ⟹  S_i+1∈3,4S\_i=3\implies S\_{i+1}\in\\{3,4\\} (1≤i\<N)(1\leq i\<N)
  • S_i=4  ⟹  S_i+1∈4,1S\_i=4\implies S\_{i+1}\in\\{4,1\\} (1≤i\<N)(1\leq i\<N)
  • 모든 질문에서 1≤l≤r≤N1\leq l\leq r\leq N이어야 한다.
  • 인터랙터는 비적응적이다. 수열 SS는 사전에 결정되어 있고, 질문에 따라 변하지 않는다.

힌트

출력 버퍼를 비우는 방법은 다음과 같다.

  • C: fflush(stdout)
  • C++: std::cout << std::flush
  • Java: System.out.flush()
  • Python: sys.stdout.flush()

이외의 언어에 대해서는 언어별 명세를 참고해야 한다.

예제1

  1. 예제 1

    입력
    1
2

0

0 0 0 2
    예상 출력
    

diff 1 2

count 1 2

answer 2 0 0 0