D - At Most 3 (Contestant ver.) Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

整数 W が与えられます。
あなたは以下の条件をすべて満たすようにいくつかのおもりを用意することにしました。

  • おもりの個数は 1 個以上 300 個以下である。
  • おもりの重さは 10^6 以下の正整数である。
  • 1 以上 W 以下のすべての正整数は 良い整数 である。ここで、以下の条件を満たす正整数 n を良い整数と呼ぶ。
    • 用意したおもりのうち \bf{3} 個以下 の異なるおもりを自由に選んで、選んだおもりの重さの和を n にすることができる。 　

条件を満たすようなおもりの組を 1 つ出力してください。

制約

  • 1 \leq W \leq 10^6
  • W は整数

入力

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

W

出力

N をおもりの個数、A_i を i 番目のおもりの重さとして、以下の形式で出力せよ。答えが複数存在する場合、どれを出力しても正解とみなされる。

N
A_1 A_2 \dots A_N

ただし、N および A_1,A_2,\dots,A_N は以下の条件を満たす必要がある。

  • 1 \leq N \leq 300
  • 1 \leq A_i \leq 10^6

入力例 1

6

出力例 1

3
1 2 3

上の出力は重さ 1 のおもり、重さ 2 のおもり、重さ 3 のおもりの 3 個のおもりを用意しています。
この出力は条件を満たしています。特に 3 番目の条件について、以下のようにおもりを選ぶことで 1 以上 W 以下の整数すべてが良い整数であることが確認できます。

  • 1 番目のおもりのみを選ぶと、重さの和は 1 になる。
  • 2 番目のおもりのみを選ぶと、重さの和は 2 になる。
  • 3 番目のおもりのみを選ぶと、重さの和は 3 になる。
  • 1 番目と 3 番目のおもりを選ぶと、重さの和は 4 になる。
  • 2 番目と 3 番目のおもりを選ぶと、重さの和は 5 になる。
  • 1 番目、2 番目と 3 番目のおもりを選ぶと、重さの和は 6 になる。

入力例 2

12

出力例 2

6
2 5 1 2 5 1

同じ重さのおもりを 2 個以上用意しても良いです。

Score : 400 points

Problem Statement

You are given an integer W.
You are going to prepare some weights so that all of the conditions below are satisfied.

  • The number of weights is between 1 and 300, inclusive.
  • Each weight has a mass of positive integer not exceeding 10^6.
  • Every integer between 1 and W, inclusive, is a good integer. Here, a positive integer n is said to be a good integer if the following condition is satisfied:
    • We can choose at most 3 different weights from the prepared weights with a total mass of n.

Print a combination of weights that satisfies the conditions.

Constraints

  • 1 \leq W \leq 10^6
  • W is an integer.

Input

Input is given from Standard Input in the following format:

W

Output

Print in the following format, where N is the number of weights and A_i is the mass of the i-th weight. If multiple solutions exist, printing any of them is accepted.

N
A_1 A_2 \dots A_N

Here, N and A_1,A_2,\dots,A_N should satisfy the following conditions:

  • 1 \leq N \leq 300
  • 1 \leq A_i \leq 10^6

Sample Input 1

6

Sample Output 1

3
1 2 3

In the output above, 3 weights with masses 1, 2, and 3 are prepared.
This output satisfies the conditions. Especially, regarding the 3-rd condition, we can confirm that every integer between 1 and W, inclusive, is a good integer.

  • If we choose only the 1-st weight, it has a total mass of 1.
  • If we choose only the 2-nd weight, it has a total mass of 2.
  • If we choose only the 3-rd weight, it has a total mass of 3.
  • If we choose the 1-st and the 3-rd weights, they have a total mass of 4.
  • If we choose the 2-nd and the 3-rd weights, they have a total mass of 5.
  • If we choose the 1-st, the 2-nd, and the 3-rd weights, they have a total mass of 6.

Sample Input 2

12

Sample Output 2

6
2 5 1 2 5 1

You may prepare multiple weights with the same mass.