만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

싱글 플레이어 게임

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

요약
숨겨진 수열에서 1, 2, 3, 4가 각각 몇 번 나오는지 구간 개수 질의와 인접 값 변화 횟수 질의로 알아내는 대화형 문제입니다.
난이도

보통10점 중 5점

유형
구현, 누적 합
정답자
아직 제출이 없습니다

문제

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

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

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

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

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

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

제한

  • 1≤T≤1001\leq T\leq 100
  • 1≤N≤10001\leq N\leq 1000
  • S1=1S_1=1
  • 1≤Si≤41\leq S_i\leq 4 (2≤i≤N2\leq i\leq N)
  • Si=1  ⟹  Si+1∈{1,2}S_i=1 \implies S_{i+1}\in\{1,2\} (1≤i<N1\leq i<N)
  • Si=2  ⟹  Si+1∈{2,3}S_i=2 \implies S_{i+1}\in\{2,3\} (1≤i<N1\leq i<N)
  • Si=3  ⟹  Si+1∈{3,4}S_i=3 \implies S_{i+1}\in\{3,4\} (1≤i<N1\leq i<N)
  • Si=4  ⟹  Si+1∈{4,1}S_i=4 \implies S_{i+1}\in\{4,1\} (1≤i<N1\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