시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 1024 MB9432812.500%

문제

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$.

서브태스크

번호배점제한
110

The value of $k$ returned by paint can be no greater than $1000$.

215

The value of $k$ returned by paint can be no greater than $100$.

320

The value of $k$ returned by paint can be no greater than $70$.

455

The value of $k$ returned by paint can be no greater than $10$.

첨부

제출할 수 있는 언어

C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)

채점 및 기타 정보

  • 예제는 채점하지 않는다.