정사각형 칠하기

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

요약

정사각형을 검은색이나 흰색으로 칠하고, 길이 k인 어떤 구간의 색 배열과 구간이 범위를 벗어나는지 여부만으로 그 시작 위치를 항상 알아낼 수 있게 하는 최소 k를 구한다.

난이도: 어려움10점 중 8점
유형: 문자열, 조합론, 그리디, 구현
정답자: 아직 제출이 없습니다

문제

Mike는 Peter와 게임을 한다. 땅 위에 $n$ 개의 정사각형이 한 줄로 그려져 있고, 왼쪽에서 오른쪽으로 $0$ 부터 $n-1$ 까지 번호가 매겨져 있다. 게임이 시작할 때 Peter는 각 정사각형을 검은색 또는 흰색 중 하나로 칠할 수 있다. 그다음 Mike에게 양의 정수 $k$ ( $1 \leq k \leq n$ )를 하나 준다.

이 게임은 총 $q$ 라운드 동안 진행된다. 각 라운드에서 Mike는 정사각형 $x$ ( $0 \leq x \lt n$ )를 무작위로 고르고, 위치 $x$ 부터 $x+k-1$ 까지의 정사각형 색을 Peter에게 알려준다. 이 위치 중 범위를 벗어난 것이 있으면 Mike는 그 사실도 함께 알려준다. 그러면 Peter는 이 정보만으로 $x$ 를 정확히 알아내야 한다.

Peter는 Mike에게 좋은 인상을 주고 싶어 하므로 $k$ 를 가능한 한 작게 정하려 한다. Peter가 최소한의 $k$ 로 이 게임을 이길 수 있는 전략을 세우도록 도와주자.

제한

$1 \leq r \leq 10$
$2 \leq n, q \leq 1000$
$-1 \leq c[i] \leq 1$ ( $0 \leq i \lt k$ )

예제1

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