20085번 - Detecting Molecules 서브태스크다국어언어 제한함수 구현

문제

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 w₀ ..., w_n-1. The detection is successful if there is a set of distinct indices I = {i₁, ..., i_m} such that l ≤ w_i1 + ... +w_im ≤ u.

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 - l ≥ w_max - w_min, where w_max = max(w₀, ..., w_n-1) and w_min = min(w₀, ..., w_n-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 w₁ + w₃ = 8 + 7 = 15, so the function can return [1, 3]. Other possible correct answers are [1, 2] (w₁ + w₂ = 8 + 8 = 16) and [2, 3] (w₂ + w₃ = 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].

서브태스크

힌트

샘플 그레이더

The sample grader reads the input in the following format:

• line 1: integers n, l, u.
• line 2: n integers: w₀, ..., w_n-1.

첨부

• molecules.h
• molecules.cpp
• grader.cpp
• 01.in
• 01.out
• 02.in
• 02.out
• 03.in
• 03.out