시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4 초 | 1024 MB | 94 | 32 | 8 | 12.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)
find_location
.
int find_location(int n, int c[])
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,find_location
is not called.During the second run of the program:
find_location
may be called multiple times,find_location
are those produced by a call to paint
for an arbitrarily chosen scenario from the first run,paint
is not called.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$.
번호 | 배점 | 제한 |
---|---|---|
1 | 10 | The value of $k$ returned by |
2 | 15 | The value of $k$ returned by |
3 | 20 | The value of $k$ returned by |
4 | 55 | The value of $k$ returned by |
C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)