사각형 칠하기 (squares)

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

이 게임은 총 $q$개의 라운드로 진행된다. 각 라운드에서 Mike는 정사각형 $x$ ($0 \leq x < n$)를 무작위로 선택하고, 위치 $x$부터 $x+k-1$까지의 정사각형들의 색을 Peter에게 알려준다. 이 위치들 중 범위를 벗어나는 것이 있다면 Mike는 그 사실도 Peter에게 알려준다. 그러면 Peter는 오직 이 정보만을 바탕으로 $x$를 정확하게 알아내야 한다.

Peter는 Mike에게 깊은 인상을 주고 싶기 때문에 가능한 한 작은 $k$의 값을 선택하고자 한다. Peter가 가능한 최소의 $k$ 값으로 이 게임에서 이길 수 있는 전략을 세우도록 도와주자.

구현 세부사항

다음 프로시저를 구현해야 한다.

int[] paint(int n)

• $n$: 정사각형의 수.
• 이 프로시저는 크기가 $n+1$인 배열 하나를 반환해야 한다. 배열의 처음 $n$개 원소는 $n$개 정사각형의 색을 나타낸다. 배열의 $i$번째 원소는 $i$번째 정사각형을 흰색으로 칠할 경우 $1$, 검은색으로 칠할 경우 $0$으로 설정해야 한다. 배열의 마지막 원소는 $k$의 값이다.
• 이 프로시저는 각 시나리오에서 find_location이 호출되기 전에 정확히 한 번 호출된다.

int find_location(int n, int c[])

• $n$: 정사각형의 수.
• $c$: 크기가 $k$인 배열. 배열의 $i$번째 원소는 $(i+x)$번째 정사각형이 흰색으로 칠해져 있으면 $1$, 검은색으로 칠해져 있으면 $0$으로 설정된다. $(i+x)$번째 정사각형이 존재하지 않으면 배열의 $i$번째 원소는 $-1$로 설정된다.
• 이 프로시저는 알아낸 $x$의 값을 반환해야 한다.
• 이 프로시저는 각 시나리오에서 각 라운드마다 한 번씩, 정확히 $q$번 호출된다.

각 테스트 케이스는 여러 개의 독립적인 시나리오, 즉 서로 다른 $n$의 값을 포함할 수 있다. $r$개의 시나리오를 포함하는 테스트 케이스에서는 위 프로시저들을 호출하는 프로그램이 다음과 같이 정확히 두 번 실행된다.

프로그램의 첫 번째 실행에서는 다음과 같다.

• paint 프로시저가 $r$번 호출되고,
• 반환된 색들과 $k$의 값이 채점 시스템에 저장되며,
• find_location은 호출되지 않는다.

프로그램의 두 번째 실행에서는 다음과 같다.

• find_location이 여러 번 호출될 수 있고,
• 각 find_location 호출에 주어지는 $n$의 값과 색들은 첫 번째 실행에서 임의로 선택된 시나리오에 대해 호출된 paint가 생성한 것들이며,
• paint는 호출되지 않는다.

예제

다음 호출을 생각해 보자.

paint(5)

정사각형은 총 $5$개이다. Peter는 정사각형들을 순서대로 검은색, 검은색, 흰색, 검은색, 흰색으로 칠할 수 있으며, $x$의 값을 알아내는 데 $k=3$이면 충분하다고 결정할 수 있다. 이 경우 프로시저는 [$0$, $0$, $1$, $0$, $1$, $3$]을 반환해야 한다.

그런 다음 find_location이 여러 번 호출된다.

가능한 호출 하나를 생각해 보자.

find_location(5, [0, 1, 0])

이는 $x$번째, $(x+1)$번째, $(x+2)$번째 정사각형의 색이 각각 검은색, 흰색, 검은색이라는 뜻이다. Peter는 이 정보로부터 $x=1$임을 알아낼 수 있다. 따라서 프로시저는 $1$을 반환해야 한다.

가능한 다른 호출을 생각해 보자.

find_location(5, [1, 0, 1])

이는 $x$번째, $(x+1)$번째, $(x+2)$번째 정사각형의 색이 각각 흰색, 검은색, 흰색이라는 뜻이다. Peter는 이 정보로부터 $x=2$임을 알아낼 수 있다. 따라서 프로시저는 $2$를 반환해야 한다.

제약 조건

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

서브태스크

1. (10점) paint가 반환하는 $k$의 값은 $1000$ 이하여야 한다.
2. (15점) paint가 반환하는 $k$의 값은 $100$ 이하여야 한다.
3. (20점) paint가 반환하는 $k$의 값은 $70$ 이하여야 한다.
4. (55점) paint가 반환하는 $k$의 값은 $30$ 이하여야 한다.

서브태스크 4에서는 부분 점수를 받을 수 있다. 모든 시나리오에서 paint가 반환한 $k$의 값 중 최댓값을 $m$이라고 하자. 이 서브태스크의 점수는 다음 표에 따라 계산된다.

샘플 그레이더는 다음 형식으로 입력을 읽는다.

• $1$번째 줄: $\;\;r$

이후 각각 하나의 시나리오를 설명하는 $r$개의 블록이 주어진다. 각 블록의 형식은 다음과 같다.

• $1$번째 줄: $\;\;n\;\;q$
• $2+i$번째 줄 ($0 \leq i \leq q-1$): find_location의 $i$번째 호출에 대한 $x$의 값.

샘플 그레이더는 다음 형식으로 출력한다.

• $1$번째 줄: $\;\;m$

이후 입력에 연속해서 주어진 시나리오들에 대응하는 $r$개의 블록이 출력된다. 각 블록의 형식은 다음과 같다.

• $1+i$번째 줄 ($0 \leq i \leq q-1$): find_location의 $i$번째 호출이 반환한, 알아낸 $x$의 값.

샘플 그레이더를 실행할 때마다 paint와 find_location이 모두 호출된다는 점에 유의하라.