No.688 E869120 and Constructing Array 2

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 256 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 117
作問者 : e869120e869120 / テスター : はむこはむこ
0 ProblemId : 1684 / 出題時の順位表

問題文

以下のような数列 $b$ を構築してください.

  • $b$ の中から $0$ 個以上の数を選ぶ. 数列の長さが $N$ のとき, 選び方は $2^N$ 通りある.
  • 選んだ数の合計が $2$ となるような選び方は, ちょうど $K$ 通りである.
  • $b_i$ は $0$ か $1$ でなければならない.
  • 数列の長さ $N$ は $1$ 以上 $30$ 以下でなければならない.

入力

K

1 行に, $0$ 以上 $1 \ 000 \ 000 \ 000$ 以下の整数 $K$ が与えられる.
ただし, $K$は条件を満たす数列が存在するものであることが保証される.

出力

N
$b_1, b_2, b_3, ..., b_N$

$1$ 行目に, 数列 $b$ の長さ $N$ を出力すること.
$2$ 行目に, 数列の値を空白区切りで出力すること.
最後に改行をすること.

サンプル

サンプル1
入力
4
出力
4
0 0 1 1

以下のような $4$ 通りの選び方ができます.

  • $3$, $4$ 番目を選ぶ.
  • $1$, $3$, $4$ 番目を選ぶ.
  • $2$, $3$, $4$ 番目を選ぶ.
  • $1$, $2$, $3$, $4$ 番目を選ぶ.

サンプル2
入力
80
出力
8
0 1 0 1 1 0 1 1

ちょうど $80$ 通りの総和が $2$ になる選び方が存在します.

サンプル3
入力
96
出力
8
0 1 0 1 1 0 1 0

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。