시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB57302767.500%

## 문제

Petr is working for a company that has built a machine for detecting molecules. Each molecule has a positive integer weight. The machine has a detection range [l, u], where l and u are positive integers. The machine can detect a set of molecules if and only if this set contains a subset of the molecules with total weight belonging to the machine's detection range.

Formally, consider n molecules with weights w0 ..., wn-1. The detection is successful if there is a set of distinct indices I = {i1, ..., im} such that lwi1 + ... +wimu.

Due to specifics of the machine, the gap between l and u is guaranteed to be greater than or equal to the weight gap between the heaviest and the lightest molecule. Formally, u - lwmax - wmin, where wmax = max(w0, ..., wn-1) and wmin = min(w0, ..., wn-1).

Your task is to write a program which either finds any one subset of molecules with total weight within the detection range, or determines that there is no such subset.

## 구현

You should implement one function (method):

• int[] find_subset(int l, int u, int[] w)
• l and u: the endpoints of the detection range,
• w: weights of the molecules.
• if the required subset exists, the function should return an array of indices of molecules that form any one such subset. If there are several correct answers, return any of them.
• if the required subset does not exist, the function should return an empty array.

Your program may write the indices into the returned array in any order.

## 예제 1

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

In this example we have four molecules with weights 6, 8, 8 and 7. The machine can detect subsets of molecules with total weight between 15 and 17, inclusive. Note, that 17 - 15 ≥ 8 - 6. The total weight of molecules 1 and 3 is w1 + w3 = 8 + 7 = 15, so the function can return [1, 3]. Other possible correct answers are [1, 2] (w1 + w2 = 8 + 8 = 16) and [2, 3] (w2 + w3 = 8 + 7 = 15).

## 예제 2

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

In this example we have four molecules with weights 5, 5, 6 and 6, and we are looking for a subset of them with total weight between 14 and 15, inclusive. Again, note that 15 - 14 ≥ 6 - 5. There is no subset of molecules with total weight between 14 and 15 so the function should return an empty array.

## 예제 3

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

In this example we have four molecules with weights 15, 17, 16 and 18, and we are looking for a subset of them with total weight between 10 and 20, inclusive. Again, note that 20 - 10 ≥ 18 - 15. Any subset consisting of exactly one element has total weight between 10 and 20, so the possible correct answers are: [0], [1], [2] and [3].

## 서브태스크

번호 배점 제한
1 9

1 ≤ n ≤ 100, 1 ≤ wi ≤ 100, 1 ≤ u, l ≤ 1,000, all wi are equal.

2 10

1 ≤ n ≤ 100, 1 ≤ wi, u, l ≤ 1,000 and max(w0, ..., wn-1) - min(w0, ..., wn-1) ≤ 1.

3 12

1 ≤ n ≤ 100, 1 ≤ wi, u, l ≤ 1,000.

4 15

1 ≤ n ≤ 10,000, 1 ≤ wi, u, l ≤ 10,000.

5 23

1 ≤ n ≤ 10,000, 1 ≤ wi, u, l ≤ 500,000.

6 31

1 ≤ n ≤ 200,000, 1 ≤ wi, u, l < 231.

## 샘플 그레이더

• line 1: integers n, l, u.
• line 2: n integers: w0, ..., wn-1.

## 제출할 수 있는 언어

C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)

## 채점 및 기타 정보

• 예제는 채점하지 않는다.