P15562 [CCPC 2025 哈尔滨站] 01 背包

01 背包问题是一个算法竞赛中经典的组合优化的问题，小 w 学会了一种求解该问题的贪心算法。01 背包问题的定义以及小 w 的贪心算法如下。 $\textbf{01 背包问题}$： 给定 $n$ 个物品，物品的重量分别为正整数 $w_1,w_2,\ldots,w_n$ ，物品的价值分别为正整数 $v_1,v_2,\ldots,v_n$，再给定背包容量 $W$。要求 $x_1,x_2,\ldots,x_n$ ($\forall 1 \le i \le n$, $x_i \in \{0,1\}$)，满足： $$ \sum_{i=1}^n w_ix_i \le W $$ 并最大化： $$ V = \sum_{i=1}^n v_ix_i $$ $\textbf{贪心算法}$： 1. 将 $n$ 个物品按照 $\frac{v_i}{w_i}$ 的值从大到小排序，$\frac{v_i}{w_i}$ 相同则按照 $w_i$ 从大到小排序。 2. 设一初始置 0 的变量 $W_0$，并，并从 $1$ 到 $n$ 枚举 $i$，如果 $V_0+w_i \le W$，则置 $x_i \leftarrow 1, W_0 \leftarrow W_0 + w_i$，否则置 $x_i \leftarrow 0$。 3. 枚举完之后即可得到所求的 $x_1,x_2,\ldots,x_n$ 以及 $V$。 你当然知道这个算法是错误的，但小 w 并不相信。即使你给了小 w 一些反例，小 w 依然认为这个算法能在很多不同的 $W$ 下都能得到最优的 $V$，所以你现在希望构造一组 $w_1,w_2,\ldots,w_n$ 以及 $v_1,v_2,\ldots,v_n$ 使得： 1. $\forall 2 \le W \le W_{lim}$（$W_{lim}$ 是一个给定的常数），小 w 的算法都无法得到最优的 $V$。 2. 在满足条件 $1$ 的情况下，$n$ 尽量小。 3. 在满足条件 $1,2$ 的情况下，$\max(w_1,w_2,\ldots,w_n)$ 尽量小。 4. 在满足条件 $1,2,3$ 的情况下，$\max(v_1,v_2,\ldots,v_n)$ 尽量小。 现在你需要构造一组满足上述条件的 01 背包来说服小 w，你能做到吗？如果构造方法有多种，你可以输出任意一种。

输入共一行包含一个整数 $W_{lim}$ ($2 \le W_{lim} \le 5 \times 10^3$)，表示 $W$ 的上界。

输出第一行包含一个整数 $n$ ($1 \le n \le 10^4$)，表示构造的 01 背包的物品数量。 第二行输出 $n$ 个整数 $w_1,w_2,\ldots,w_n$ ($1 \le w_i \le W_{lim}$) 表示物品的重量。 第三行输出 $n$ 个整数 $v_1,v_2,\ldots,v_n$ ($1 \le v_i \le 10^9$) 表示物品的价值。 可以证明，在给定的问题以及输入条件下，总能找到满足上述数据范围的解。