/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 6 点
注意
この問題に対する言及は、2021/7/17 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。
問題文
正整数 N を、相異なる 3 べきの和差で表してください。
形式的には、以下の条件をすべて満たす数列 A を構築してください。
- A の長さを M として、1 \leq M \leq 100
- \sum_{i=1}^{M}A_i = N
- |A_i| \leq 10^{18}
- 各 i\ (1 \leq i \leq M) について、|A_i| は 3 べき。即ち、ある非負整数 x を用いて |A_i|=3^x と表すことができる。
- |A_i| \neq |A_j|\ (i \neq j)
この問題の制約下で、このような数列 A の存在は保証されます。
制約
- 1 \leq N \leq 10^{15}
- N は整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
以下の形式で問題文中の条件を満たす数列 A を出力せよ。問題文同様、M は A の長さを表す。
M A_1 A_2 \ldots A_M
条件を満たす A が複数存在する場合、そのいずれを出力してもよい。
入力例 1
6
出力例 1
2 9 -3
9 と 3 は共に 3 べきであり、また 9+(-3)=6 であるため、この出力は問題文中の条件を満たします。
入力例 2
9193
出力例 2
9 2187 27 1 -243 3 9 -81 6561 729
入力例 3
10120190919012
出力例 3
16 -1594323 9 -177147 -531441 1162261467 -4782969 387420489 -6561 -2187 2541865828329 -27 7625597484987 3486784401 10460353203 -94143178827 31381059609
入力が 32 bit 整数型に収まりきらない場合があります。
Score : 6 points
Warning
Do not make any mention of this problem until July 17, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).
Problem Statement
Represent a positive integer N by additions and subtractions of distinct powers of 3.
Formally, construct a sequence A that satisfies all of the following conditions.
- 1 \leq M \leq 100, where M is the length of A.
- \sum_{i=1}^{M}A_i = N.
- |A_i| \leq 10^{18}.
- For each i\ (1 \leq i \leq M), |A_i| is a power of 3. That is, there is a non-negative integer x such that |A_i|=3^x.
- |A_i| \neq |A_j|\ (i \neq j).
It is guaranteed that such a sequence A exists under the Constraints of this problem.
Constraints
- 1 \leq N \leq 10^{15}
- N is an integer.
Input
Input is given from Standard Input in the following format:
N
Output
Print a sequence A that satisfies the conditions in the Problem Statement in the format below, where M again denotes the length of A.
M A_1 A_2 \ldots A_M
If there are multiple sequences A satisfying the conditions, you may print any of them.
Sample Input 1
6
Sample Output 1
2 9 -3
Both 9 and 3 are powers of 3, and we have 9+(-3)=6, so this output satisfies the conditions.
Sample Input 2
9193
Sample Output 2
9 2187 27 1 -243 3 9 -81 6561 729
Sample Input 3
10120190919012
Sample Output 3
16 -1594323 9 -177147 -531441 1162261467 -4782969 387420489 -6561 -2187 2541865828329 -27 7625597484987 3486784401 10460353203 -94143178827 31381059609
Input may not fit into a 32-bit integer type.