102513: [AtCoder]ABC251 D - At Most 3 (Contestant ver.)

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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.

Input

题意翻译

给你整数 $W(1 \le W \le 10^6)$。 你必须构造一个数组 $a$,包含最多 $300$ 个元素,使得小于等于 $W$ 的所有正整数都可以被 $a$ 数组的元素相加表示出来。

Output

分数:400分

问题描述

给你一个整数$W$。

  • 准备的砝码数量在$1$到$300$之间,包括$1$和$300$。
  • 每个砝码的质量是一个不超过$10^6$的正整数。
  • 从$1$到$W$之间的每个整数都是一个好整数。在这里,如果满足以下条件,则正整数$n$被称为好整数:
    • 我们可以从准备的砝码中选择最多$3$个不同重量的砝码,其总重量为$n$。

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

约束

  • $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

你可以准备多个质量相同的砝码。

加入题单

上一题 下一题 算法标签: