彼得在一家公司工作，这家公司已经制造了一台检测分子的机器。每个分子的重量都是正整数。这台机器的检测范围是 $[l,u]$，这里 $l$ 和 $u$ 都是正整数。这台机器能够检测一个分子集合当且仅当这个集合包含了一个子集，这个子集的分子的重量属于机器的检测范围。

考虑 $n$ 个分子，重量记为 $w_0,\dots ,w_{n-1}$。如果存在一个下标的集合（并且该集合中的下标都不相同）$I=\{i_1,\dots ,i_m\}$ 使得 $l\le w_{i_1}+\cdots +w_{i_m}\le u$，那么检测就会成功。

由于机器的细节，$l$ 和 $u$ 之间的差距要保证会大于等于最重分子和最轻分子之间的差距，即 $u-l\ge w_{max}-w_{min}$，其中 $w_{max}=max(w_0,\dots ,w_{n-1})$，$w_{min}=min(w_0,\dots ,w_{n-1})$。

你的任务是写一个程序，该程序能找到一个子集，使得该子集的总重量属于检测范围，或者判定没有这样的子集存在。

实现细节

你应该实现一个函数（方法）：

• std::vector<int> find_subset(int l, int u, std::vector<int> w)
  • $l$ 和 $u$：分别表示检测范围的两个端点，
  • $w$：分子的重量。
  • 如果存在符合要求的子集，该函数应该返回一个数组，数组中的元素代表符合要求的子集中的分子的下标。如果存在多个正确答案，返回任何一个子集即可。
  • 如果不存在符合要求的子集，该函数应该返回一个空数组。

你的程序可以将分子的下标以任何顺序写入返回的数组中。

请使用提供的模板文件，参考关于你所使用的编程语言的实现细节。

样例一

find_subset(15, 17, [6, 8, 8, 7])

这个例子当中，我们有四个分子，重量分别是 $6,8,8$ 和 $7$。这台机器可以检测子集总重量在 $15$ 到 $17$ 之间（包含 $15$ 和 $17$）的子集。注意，$17-15\ge 8-6$。分子 1 和分子 3 的重量之和为 $w_1+w_3=8+7=15$, 所以这个函数应该返回 $[1,3]$。其他可能正确的答案有 $[1,2]$（$w_1+w_2=8+8=16$）和 $[2,3]$（$w_2+w_3=8+7=15$）。

样例二

find_subset(14, 15, [5, 5, 6, 6])

这个例子当中，我们有四个分子，重量分别为 $5,5,6$ 和 $6$，我们要寻找一个子集，其总重量介于 $14$ 和 $15$ 之间（包含 $14$ 和 $15$）。请注意，$15-14\ge 6-5$。因为不存在总重量介于 $14$ 和 $15$ 之间的子集，所以该函数返回空数组。

样例三

find_subset(10, 20, [15, 17, 16, 18])

这个例子当中，我们有四个分子，重量分别为 $15,17,16$ 和 $18$，而且我们要寻找一个子集，其总重量介于 $10$ 和 $20$ 之间（包含 $10$ 和 $20$）。请注意，$20-10\ge 18-15$。任何只包含一个元素的子集，其重量都在 $10$ 和 $20$ 之间，所以可能正确的答案有 $[0],[1],[2]$ 和 $[3]$。

子任务

评测方式

评测程序将会按照下列格式读取输入数据：

• 第一行：整数 $n,l$ 和 $u$。
• 第二行：$n$ 个整数：$w_0,\dots ,w_{n-1}$。

交互式类型的题目怎么本地测试

时间限制：$1\mathtt{\text{s}}$

空间限制：$2\mathtt{\text{GB}}$

下载

样例及测评库下载