28274번 - Uttered-Verified 서브태스크언어 제한함수 구현

문제

커다란 호수 근처에 크루즈니 마을이 자리 잡고 있다. 크루즈니 마을에는 총 $N$개의 집이 있는데 각 집의 번호는 시계 방향으로 0ドル$번부터 $N-1$번까지 붙어있다.

크루즈니 마을 사람들은 입주를 하면서 에코백을 하나씩 받는데, 각 집마다 한별이 에코백 또는 니키 에코백 중 하나를 선택해서 받는다. 크루즈니 마을 사람들은 서로 교류를 하면서 자기를 포함하여 시계 방향으로 $K$개의 집이 받은 에코백의 종류를 알게 되었다. 즉, $i$번 집 주민은 $i,ドル $(i+1) \bmod N,ドル ..., $(i+K-1) \bmod N$번 집이 받은 에코백의 종류를 알고 있다.

기자 성훈이는 크루즈니 마을에서 뉴스를 보도하고 있다. 성훈이가 보도하기 앞서 $N$개 집에서 받은 에코백의 종류를 미리 확보해놓았다. 성훈이는 크루즈니 마을의 에코백 성향에 대하여 보도를 하는데 보도 내용은 다음과 같다.

• $A$번 집은 $B$번 집과 같은 에코백을 받았다.
• $A$번 집과 $B$번 집이 받은 에코백의 종류가 다르다.

성훈이는 가짜 뉴스에 따른 마을 구성원들의 변화를 실험해보기 위해 일부 뉴스를 거짓으로 보도하려고 한다. 처음에는 마을 사람들은 제한적인 정보만 알고 있기 때문에 처음에는 성훈이가 가짜 뉴스를 보도하는지 모른다. 성훈이의 보도가 여러 개 모이면 일부 마을 사람들은 성훈이가 보도한 뉴스와 자기가 알고 있는 정보를 바탕으로 마을 사람들의 에코백 종류를 예측하다가 가능한 경우가 없다는 것을 확인한다. 그렇게 되면 마을 사람들은 모순을 느끼고 성훈이의 뉴스를 믿지 않게 된다.

성훈이는 매 보도를 할 때 몇 개의 집에서 모순을 느끼게 되는지 알아보려고 한다. 성훈이를 도와 모순을 느끼는 집을 예측하는 프로그램을 작성하여라.

함수 목록 및 정의

여러분은 아래 함수를 구현해야 한다.

void init(int[] T, int K)

• $T$: 길이가 $N$인 배열. 마을의 $i$번 집은 한별이 에코백($T[i] = 0$인 경우)이나 니키 에코백($T[i] = 1$인 경우)을 갖고 있다. (0ドル \leq i < N$)
• $K$: 마을의 각 집이 알고 있는 이웃의 수.
• 이 함수는 utter 함수가 호출되기 전에 한 번 호출된다. 해당 함수에서 전처리 등의 작업을 할 수 있다.

int utter(int A, int B, int V)

• $A, B$: 성훈이가 보도하는 두 집의 번호 $A, B$이다. (0ドル \leq A < B < N$)
• $V$: 두 집이 같은 에코백을 받았다고 보도했으면 $V = 0$이고 그렇지 않으면 $V = 1$이다.
• 이 함수는 성훈이가 "$A$번 집과 $B$번 집은 같은/다른 에코백을 받았다"라고 보도한 이후 모순을 느끼는 집의 수를 반환해야 한다. 이 함수는 $Q$번 호출된다.

제출하는 소스 코드의 어느 부분에서도 입출력 함수를 실행해서는 안 된다.

입력

출력

제한

서브태스크

힌트

예제 1

$T = [0, 1, 1, 0, 1],ドル $K = 3$인 경우를 생각해보자. 맨 처음에 init([0, 1, 1, 0, 1], 3)이 호출된다.

성훈이가 "1ドル$번 집과 3ドル$번 집은 서로 다른 에코백을 받았다"라고 보도하면 utter(1, 3, 1)이 호출된다. 마을 주민 5ドル$명은 모두 1ドル$번 집과 3ドル$번 집의 에코백 종류를 알 수 있으며, 이 과정에서 모순을 느끼는 사람이 없으므로 해당 함수는 0ドル$을 반환해야 한다.

성훈이가 "0ドル$번 집과 3ドル$번 집은 서로 다른 에코백을 받았다"라고 보도하면 utter(0, 3, 1)이 호출된다. 0ドル$번, 3ドル$번, 4ドル$번 마을 주민은 모순을 느끼며, 1ドル$번 마을 주민은 0ドル,ドル 1ドル,ドル 2ドル,ドル 3ドル$번 마을 주민의 에코백 종류를 알 수 있으며, 2ドル$번 마을 주민은 모든 마을 주민의 에코백 종류를 알 수 있다. 따라서 해당 함수는 3ドル$을 반환해야 한다.

성훈이가 마지막으로 "3ドル$번 집과 4ドル$번 집은 서로 같은 에코백을 받았다"라고 보도하면 utter(3, 4, 0)이 호출된다. 2ドル$번 마을 주민이 추가로 모순을 느끼며 1ドル$번 마을 주민은 여전히 모순을 느끼지 않는다. 따라서 해당 함수는 4ドル$를 반환해야 한다.

샘플 그레이더

샘플 그레이더는 첫 번째 줄에 $N,ドル $K,ドル $Q$를 입력받는다. 두 번째 줄에는 $T[i]$에 해당하는 $N$개의 정수를 입력받는다. 세 번째 줄부터 $Q$개의 줄에는 각 utter() 호출의 인자 $A,ドル $B,ドル $V$를 입력받는다.

샘플 그레이더는 utter() 호출의 반환값을 출력한다.

첨부

• uttered_verified.zip