G - Power Expression

Contest Duration: 2021-07-03(Sat) 04:00 - 2021-07-03(Sat) 09:00 (local time) (300 minutes) Back to Home

G - Power Expression Editorial

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$ が複数存在する場合、そのいずれを出力してもよい。

入力例 1Copy

Copy

出力例 1Copy

Copy

2
9 -3

$9$ と $3$ は共に $3$ べきであり、また $9+(-3)=6$ であるため、この出力は問題文中の条件を満たします。

入力例 2Copy

Copy

出力例 2Copy

Copy

9
2187 27 1 -243 3 9 -81 6561 729

入力例 3Copy

Copy

10120190919012

出力例 3Copy

Copy

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 1Copy

Copy

Sample Output 1Copy

Copy

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 2Copy

Copy

Sample Output 2Copy

Copy

9
2187 27 1 -243 3 9 -81 6561 729

Sample Input 3Copy

Copy

10120190919012

Sample Output 3Copy

Copy

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.