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

考虑 $n$ 个分子，重量记为 $w_0, \ldots, w_{n - 1}$。如果存在一个下标的集合（并且该集合中的下标都不相同）$I = \{i_1, \ldots, 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, \ldots, w_{n - 1})$，$w_{\min} = \min(w_0, \ldots, 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, \ldots, w_{n - 1}$。

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

时间限制：$1\texttt{s}$

空间限制：$2\texttt{GB}$

下载

样例及测评库下载