logo AlgoBeat OnlineJudge
登录 注册

#215564. [CCPC 2025 哈尔滨站] 01 背包

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

01 背包问题是一个算法竞赛中经典的组合优化的问题,小 w 学会了一种求解该问题的贪心算法。01 背包问题的定义以及小 w 的贪心算法如下。

给定 个物品,物品的重量分别为正整数 ,物品的价值分别为正整数 ,再给定背包容量 。要求 (, ),满足:

并最大化:

  1. 个物品按照 的值从大到小排序, 相同则按照 从大到小排序。
  2. 设一初始置 0 的变量 ,并,并从 枚举 ,如果 ,则置 ,否则置
  3. 枚举完之后即可得到所求的 以及

你当然知道这个算法是错误的,但小 w 并不相信。即使你给了小 w 一些反例,小 w 依然认为这个算法能在很多不同的 下都能得到最优的 ,所以你现在希望构造一组 以及 使得:

  1. 是一个给定的常数),小 w 的算法都无法得到最优的
  2. 在满足条件 的情况下, 尽量小。
  3. 在满足条件 的情况下, 尽量小。
  4. 在满足条件 的情况下, 尽量小。

现在你需要构造一组满足上述条件的 01 背包来说服小 w,你能做到吗?如果构造方法有多种,你可以输出任意一种。

输入格式

输入共一行包含一个整数 (),表示 的上界。

输出格式

输出第一行包含一个整数 (),表示构造的 01 背包的物品数量。

第二行输出 个整数 () 表示物品的重量。

第三行输出 个整数 () 表示物品的价值。

可以证明,在给定的问题以及输入条件下,总能找到满足上述数据范围的解。

样例

样例输入 1

2

样例输出 1

2
1 2
2 3