Score : $400$ points

问题描述

你得到一个整数 $W$。

你需要准备一些砝码，使得以下所有条件都得到满足：

• 砝码的数量在 $1$ 到 $300$（包含）之间。
• 每个砝码的质量为不超过 $10^6$ 的正整数。
• 区间 $1$ 到 $W$（包含）内的每个整数都是一个 好整数。这里，一个正整数 $n$ 如果满足以下条件，则被称为好整数：
  • 我们可以从已准备好的砝码中选择 最多 3 个 不同的砝码，使得它们的总质量为 $n$。

输出一组满足条件的砝码组合。

以上为通义千问 qwen-max 翻译，仅供参考。

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.

update @ 2024/3/10 10:43:00