← 返回题目列表

AtCoder · abc372_b

D. 3 的 A 次方

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

分数: 200 点

问题陈述

给你一个正整数 M。 求一个正整数 N 和非负整数序列 A = (A_1, A_2, \ldots, A_N) 满足以下所有条件:

  • 1 \le N \le 20
  • 0 \le A_i \le 10 (1 \le i \le N)
  • \displaystyle \sum_{i=1}^N 3^{A_i} = M

可以证明,在约束条件下,总是存在至少一对这样的 N 和 A 满足条件。

约束

  • 1 \le M \le 10^5

输入

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

M

输出

打印 N 和 A 满足以下格式的条件:

N
A_1 A_2 \ldots A_N

如果有多个有效对 N 和 A,其中任何一个都是可以接受的。


示例输入 1

6

示例输出 1

2
1 1

例如, N=2 和 A=(1,1),我们有 \displaystyle \sum_{i=1}^N 3^{A_i} = 3+3=6,满足所有条件。

另一个例子是 N=4 和 A=(0,0,1,0),也满足条件。


示例输入 2

100

示例输出 2

4
2 0 2 4

示例输入 3

59048

示例输出 3

20
0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9

注意条件 1 \le N \le 20.