103721: [Atcoder]ABC372 B - 3^A

Problem Statement

You are given a positive integer $M$. Find a positive integer $N$ and a sequence of non-negative integers $A = (A_1, A_2, \ldots, A_N)$ that satisfy all of the following conditions:

• $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$

It can be proved that under the constraints, there always exists at least one such pair of $N$ and $A$ satisfying the conditions.

Constraints

• $1 \le M \le 10^5$

Input

The input is given from Standard Input in the following format:

$M$

Output

Print $N$ and $A$ satisfying the conditions in the following format:

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

If there are multiple valid pairs of $N$ and $A$, any of them is acceptable.

Sample Input 1

6

Sample Output 1

2
1 1

For example, with $N=2$ and $A=(1,1)$, we have $\displaystyle \sum_{i=1}^N 3^{A_i} = 3+3=6$, satisfying all conditions.

Another example is $N=4$ and $A=(0,0,1,0)$, which also satisfies the conditions.

Sample Input 2

100

Sample Output 2

4
2 0 2 4

Sample Input 3

59048

Sample Output 3

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

Note the condition $1 \le N \le 20$.

题目描述

给你一个正整数 $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$。