Uttered-Verified

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

요약

원형으로 놓인 N개의 집과 두 집이 같거나 다르다는 보고가 주어질 때, 보고마다 모순을 느끼는 집의 수를 구합니다.

난이도: 보통10점 중 7점
유형: 유니온 파인드, 슬라이딩 윈도우
정답자: 아직 제출이 없습니다

문제

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

마을 사람들은 입주할 때 에코백을 하나씩 받는다. 각 집은 한별 에코백 또는 니키 에코백 중 하나를 받는다. 마을 사람들은 서로 교류하면서 자기 집을 포함해 시계 방향으로 연속한 $K$ 개 집이 받은 에코백 종류를 알게 된다. 즉, $i$ 번 집 주민은 $i$ , $(i+1) \bmod N$ , ..., $(i+K-1) \bmod N$ 번 집이 받은 에코백 종류를 안다.

기자 성훈이는 마을 뉴스를 보도한다. 보도하기 전에 성훈이는 $N$ 개 집이 받은 에코백 종류를 미리 확보해 두었다. 보도 내용은 다음 두 가지 중 하나이다.

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

성훈이는 가짜 뉴스가 마을 구성원에게 미치는 영향을 실험하려고 일부 뉴스를 거짓으로 보도한다. 마을 사람들은 처음에는 제한된 정보만 알고 있어서 뉴스가 거짓인지 알 수 없다. 보도가 여러 개 쌓이면, 일부 주민은 보도 내용과 자신이 아는 정보를 바탕으로 에코백 종류를 예측하다가 가능한 경우가 없다는 것을 확인한다. 이때 그 주민은 모순을 느끼고 성훈이의 뉴스를 믿지 않게 된다.

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

예제1

예제 1
입력
```
2 1
0 1
1
2 0 1
```
예상 출력
```
0
```