19932번 - Painting Squares 서브태스크다국어언어 제한함수 구현투 스텝

문제

Mike is playing a game with Peter. There are $n$ squares drawn on the ground in a single row, numbered 0ドル$ to $n-1$ from left to right. At the start of the game, Peter is allowed to paint each of these squares either black or white. He will then give Mike a single positive integer $k$ (1ドル \leq k \leq n$).

This game lasts a total of $q$ rounds. In each round, Mike will randomly pick a square $x$ (0ドル \leq x \lt n$), and tell Peter the colours of the squares from positions $x$ to $x+k-1$ inclusive. If any of these positions are out of range, Mike will inform Peter accordingly as well. Peter will then need to correctly deduce $x$ based purely on this information alone.

Peter wishes to impress Mike, and thus wants to pick a value of $k$ that is as low as possible. Help Peter devise a strategy to win this game with the minimum possible value of $k$.

구현

You should implement the following procedures:

int[] paint(int n)

• $n$: number of squares.
• This procedure should return a single array of size $n+1$. The first $n$ elements of the array will be the colours of the $n$ squares. The $i$-th element of the array should be set to 1ドル$ if the $i$-th square is to be painted white, or 0ドル$ if it is to be painted black. The last element of the array will be the value of $k$.
• This procedure will be called exactly once for each scenario, before any calls to find_location.

int find_location(int n, int c[])

• $n$: number of squares.
• $c$: an array of size $k$. The $i$-th element of the array is set to 1ドル$ if the ($i+x$)-th square is painted white, or 0ドル$ if it is painted black. If the ($i+x$)-th square does not exist, the $i$-th element of the array will be set to $-1$.
• This procedure should return the deduced value of $x$.
• This procedure will be called exactly $q$ times for each scenario, once for each round.

Each test case may involve multiple independent scenarios (i.e., different values of $n$). For a test case involving $r$ scenarios, a program that calls the above procedures is run exactly two times, as follows.

During the first run of the program:

• paint procedure is called $r$ times,
• the returned colours and value of $k$ are stored by the grading system, and
• find_location is not called.

During the second run of the program:

• find_location may be called multiple times,
• the value of $n$ and colours given to each call to find_location are those produced by a call to paint for an arbitrarily chosen scenario from the first run,
• paint is not called.

입력

출력

제한

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

예시

Consider the following call:

paint(5)

There are a total of 5ドル$ squares. Peter may choose to paint the squares black, black, white, black, white in that order, and decides that $k=3$ would be sufficient for him to deduce the value of $x$. In that case, the procedure should return [0ドル,ドル 0ドル,ドル 1ドル,ドル 0ドル,ドル 1ドル,ドル 3ドル$].

Several calls would then be made to find_location.

Consider a possible call:

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

This means that the colour of the $x$-th, $(x+1)$-th and $(x+2)$-th squares are black, white and black respectively. Peter could deduce from this that $x=1$. Therefore, the procedure should return 1ドル$.

Consider another possible call:

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

This means that the colour of the $x$-th, $(x+1)$-th and $(x+2)$-th squares are white, black and white respectively. Peter could deduce from this that $x=2$. Therefore, the procedure should return 2ドル$.

서브태스크

힌트

첨부

• squares.zip