問題一覧 > 通常問題

No.1376 Simple LPS Problem

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 60
作問者 : leaf_1415leaf_1415 / テスター : wotsushiwotsushi
9 ProblemId : 5304 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-11-13 14:49:36

問題文

文字列 $S$ に対して $f(S)$ を、 $S$ に連続な部分文字列として含まれる最長の回文の長さとします。
($S$ 自身も $S$ の部分文字列とみなします。)

$2$ つの正整数 $N, K$ が与えられます。
$f(S)$ がちょうど $K$ になるような、$0$ と $1$ からなる長さ $N$ の文字列 $S$ を一つ求めて下さい。
ただし、そのような文字列 $S$ が存在しない場合は、代わりに $-1$ を出力してください。

入力

$N\ K$

$1 \leq K \leq N \leq 10^5$
$N, K$ は整数

出力

$f(S)$ がちょうど $K$ になるような、$0$ と $1$ からなる長さ $N$ の文字列 $S$ を $1$ 行に出力してください。
そのような文字列が複数ある場合はどれを出力しても正解となります。
また、そのような文字列 $S$ が存在しない場合は、代わりに $-1$ を出力してください。
最後に改行してください。

サンプル

サンプル1
入力
7 4
出力
0110100

"0110100"に連続な部分文字列として含まれる最長の回文は"0110"です。
したがって、$f(0110100) = 4$ となります。

サンプル2
入力
9 3
出力
-1

$0$ と $1$ からなる長さ $9$ の文字列 $S$ で、$f(S) = 3$ となるものは存在しないので、$-1$ を出力します。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。