分数: 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.