← 返回题目列表

AtCoder · abc251_d

G. 最多3个(参赛者版)

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

给你一个整数 W.
您将准备一些重物,以满足以下所有条件。

  • 权重的数量介于 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

在上面的输出中, 3 重量与质量 1, 2,和 3 已准备好。
该输出满足条件。 特别是,关于 3-rd条件,我们可以确认之间的每个整数 1 和 W,包括在内,是一个很好的整数。

  • 如果我们只选择 1-st 重量,总质量为 1.
  • 如果我们只选择 2-nd 重量,它的总质量为 2.
  • 如果我们只选择 3-rd 重量,其总质量为 3.
  • 如果我们选择 1-st 和 3-rd 重量,它们的总质量为 4.
  • 如果我们选择 2-nd 和 3-rd 重量,它们的总质量为 5.
  • 如果我们选择 1-st, 2-nd,以及 3-rd 重量,它们的总质量为 6.

示例输入 2

12

示例输出 2

6
2 5 1 2 5 1

您可以准备多个具有相同质量的重物。