No.873 バイナリ、ヤバいなり!w

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 40
作問者 : tatyamtatyam / テスター : Shuz*Shuz*
5 ProblemId : 2743 / 出題時の順位表
問題文最終更新日: 2019-08-17 00:51:41

問題文

バイナリを「0と1のみで構成される文字列」と定義します。
01列を「隣合う文字が相異なるバイナリ」と定義します。
バイナリのヤバさを「バイナリを同じ文字が連続するところで分割したときのそれぞれの01列の長さの二乗和」と定義します。
例えば、 "01011011000" は "0101" , "101" , "10" , "0" , "0"と分割され、そのヤバさは $4^2+3^2+2^2+1^2+1^2=31$ です。
正の整数 $N$ が与えられます。ヤバさが $N$ のバイナリのうち最も長さの短いものを求めてください。
ただし、答えが複数ある場合は、そのうち辞書順最小を求めてください。

入力

$N$

入力は整数で与えられる。
$1\leq N\leq 3 \times 10^5$

出力

最後に改行してください。

サンプル

サンプル1
入力
1
出力
0

ヤバさが 1 であるバイナリは "0" と "1" で、どちらも長さが 1 ですが、辞書順最小である "0" を出力します。

サンプル2
入力
5
出力
001

サンプル3
入力
32
出力
01011010

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