At Most 3 (Contestant ver.)

题目描述

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.

输入格式

Input is given from Standard Input in the following format: $W$

输出格式

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$

6

3
1 2 3

12

6
2 5 1 2 5 1

提示

$1 \leq W \leq 10^6$ $W$ is an integer.在上面的输出中，准备了质量分别为 $1$、$2$ 和 $3$ 的 $3$ 个砝码。
该输出满足条件。尤其是，关于第 $3$ 条条件，我们可以确认每个介于 $1$ 到 $W$（含）之间的整数都是良好整数。

如果我们只选择第 $1$ 个砝码，则总质量为 $1$。 如果我们只选择第 $2$ 个砝码，则总质量为 $2$。 如果我们只选择第 $3$ 个砝码，则总质量为 $3$。 如果我们选择第 $1$ 个和第 $3$ 个砝码，则总质量为 $4$。 如果我们选择第 $2$ 个和第 $3$ 个砝码，则总质量为 $5$。 如果我们选择第 $1$、第 $2$ 和第 $3$ 个砝码，则总质量为 $6$.
你可以准备质量相同的多个砝码。

标签: AtCoder|abc251D

来源

AtCoder|abc251D