AT_abc251_d [ABC251D] At Most 3 (Contestant ver.)

题目描述

给定一个整数 $W$。
你需要准备若干个砝码，使其满足以下所有条件：

• 砝码的个数不少于 $1$ 个且不超过 $300$ 个。
• 每个砝码的重量是 $10^6$ 以内的正整数。
• 对于所有 $1$ 到 $W$ 之间的正整数，都称为好整数。这里，满足以下条件的正整数 $n$ 被称为好整数：
  • 可以从准备好的砝码中任意选择不超过 $3$ 个不同的砝码，使得所选砝码的重量之和恰好等于 $n$。

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

输入格式

输入以以下格式从标准输入读入：

$W$

输出格式

请输出 $N$（砝码的个数）以及 $A_1, A_2, \dots, A_N$（第 $i$ 个砝码的重量），格式如下：

$N$ $A_1$ $A_2$ $A_3$ $\dots$ $A_N$

其中，$N$ 和 $A_1, A_2, \dots, A_N$ 需满足以下条件：

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

输入输出样例 #1

输入 #1

6

输出 #1

3
1 2 3

输入输出样例 #2

输入 #2

12

输出 #2

6
2 5 1 2 5 1

说明/提示

限制条件

• $1 \leq W \leq 10^6$
• $W$ 是整数

样例解释 1

上面的输出准备了重 $1$、重 $2$、重 $3$ 的 $3$ 个砝码。这个输出满足所有条件。特别是关于第 $3$ 条件，可以通过如下方式选择砝码，使得 $1$ 到 $W$ 的所有整数都是好整数：

• 只选第 $1$ 个砝码，重量和为 $1$。
• 只选第 $2$ 个砝码，重量和为 $2$。
• 只选第 $3$ 个砝码，重量和为 $3$。
• 选第 $1$ 个和第 $3$ 个砝码，重量和为 $4$。
• 选第 $2$ 个和第 $3$ 个砝码，重量和为 $5$。
• 选第 $1$、第 $2$、第 $3$ 个砝码，重量和为 $6$。

样例解释 2

你也可以准备两个或更多个相同重量的砝码。

由 ChatGPT 4.1 翻译