← 返回题目列表

AtCoder · arc122_c

C. 计算器

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

Snuke 有整数 x 和 y。 最初, x=0,y=0.

Snuke 可以以任意顺序执行以下四种操作任意次数:

  • 操作 1:替换的值 x 与 x+1.

  • 操作 2:替换的值 y 与 y+1.

  • 操作 3:替换的值 x 与 x+y.

  • 操作 4:替换的值 y 与 x+y.

给你一个正整数 N。 最多做 130 操作以便 x 将具有该值 N。 在这里, y 可以具有任何值。 我们可以证明在这个问题的约束下存在这样一个操作序列。

约束

  • 1 \leq N \leq 10^{18}
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N

输出

按以下格式打印您的答案:

K
t_1
t_2
\vdots
t_K

在这里, K (0 \leq K \leq 130) 表示操作次数,并且 t_i(1 \leq t_i \leq 4) 代表 i待完成的操作。


示例输入 1

4

示例输出 1

5
1
4
2
3
1

这里,值 x 和 y 更改如下: (0,0)\rightarrow (操作 1) \rightarrow (1,0) \rightarrow (操作 4) \rightarrow (1,1) \rightarrow (操作 2) \rightarrow (1,2) \rightarrow (操作 3) \rightarrow (3,2) \rightarrow (操作 1) \rightarrow (4,2),以及最终值 x 匹配 N.