No.1376 Simple LPS Problem
Problem Statement
For a string $S$, let $f(S)$ be the length of the longest palindrome contained in $S$ as a contiguous substring.
($S$ itself is also regarded as a substring of $S$.)
You are given $2$ positive integers $N, K$.
Find one string $S$ of length $N$ consisting of $0$ and $1$ such that $f(S)$ is exactly $K$.
However, if no such string $S$ exists, output $-1$ instead.
Input
$N\ K$
$1 \leq K \leq N \leq 10^5$
$N, K$ are integers.
Output
Output, on $1$ line, a string $S$ of length $N$ consisting of $0$ and $1$ such that $f(S)$ is exactly $K$.
If there are multiple such strings, any of them will be accepted.
If no such string $S$ exists, output $-1$ instead.
Print a newline at the end.
Sample
Sample 1
Input
7 4
Output
0110100
The longest palindrome contained in "0110100" as a contiguous substring is "0110".
Therefore, $f(0110100) = 4$.
Sample 2
Input
9 3
Output
-1
There is no string $S$ of length $9$ consisting of $0$ and $1$ such that $f(S) = 3$, so output $-1$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
leaf_1415
wotsushi