E - Exactly K Triangles Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

非負整数 K が与えられます。以下の条件を満たす正整数列 A=(A_1, A_2, \ldots, A_N) を 1 つ構築してください。

  • 3 辺の長さがそれぞれ A_i, A_j, A_k である面積が正の三角形が存在するような整数組 (i, j, k) (1 \leq i < j < k \leq N) がちょうど K 個ある。

制約

  • 0 \leq K \leq 10^9
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

K

出力

以下の形式で数列 A を出力せよ。

N
A_1 A_2 \ldots A_N

ただし、これは以下の条件を満たす必要がある。

  • 1 \leq N \leq 2000
  • 1 \leq A_i \leq 10^{18}
  • 出力は全て整数
  • 3 辺の長さがそれぞれ A_i, A_j, A_k である面積が正の三角形が存在するような整数組 (i, j, k) (1 \leq i < j < k \leq N)がちょうど K 個ある。

この制約下で、どのような K に対しても条件を満たす数列 A が 1 つ以上存在することが証明できる。

条件を満たす数列 A が複数存在する場合、そのどれを出力してもよい。

入力例 1

3

出力例 1

5
1 2 3 4 5

A_i, A_j, A_k を 3 辺に持つ面積が正の三角形が存在するのは (i, j, k) = (2,3,4), (2,4,5), (3,4,5) の 3 つなので、条件を満たします。

入力例 2

0

出力例 2

3
1 10 100

入力例 3

10

出力例 3

5
10 10 10 10 10

原案: NatsubiSogan