IOI '16 - Kazan, Russia

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 operation find_subset:

• find_subset(n, l, u, w[])
  • n: the number of elements in w (i.e, the number of molecules),
  • l and u: the endpoints of the detection range,
  • w: weights of the molecules.
  • if the required subset exists, then output an array I of indices of molecules that form any one such subset. If there are several correct answers, output any of them.
  • if the required subset does not exist, then output a single number 0.

Your program may output the indices in any order.

Input Format

The input will be given in the following format:

• Line 1: three space-separated integers n, l, u
• Line 2: n space-separated integers w₀, …, w_{n − 1}

Output Format

The output should be in the following format:

• Line 1: a single integer m
• Line 2: m space-separated integers i₁, …, i_m

Sample Input 1

4 15 17
6 8 8 7

Sample Output 1

2
1 2

Explanation 1

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 program can output [1, 3]. Other possible correct answers are [1, 2] (w₁ + w₂ = 8 + 8 = 16) and [2, 3] (w₂ + w₃ = 8 + 7 = 15).

Sample Input 2

4 14 15
5 5 6 6

Sample Output 2

0

Explanation 2

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.

Sample Input 3

4 10 20
15 17 16 18

Sample Output 3

1
0

Explanation 3

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].

Subtasks

1. (9% of points): 1 ≤ n ≤ 100, 1 ≤ w_i ≤ 100, 1 ≤ u, l ≤ 1000, all w_i are equal.
2. (10% of points): 1 ≤ n ≤ 100, 1 ≤ w_i, u, l ≤ 1000 and max(w₀, …, w_{n − 1}) − min(w₀, …, w_{n − 1}) ≤ 1.
3. (12% of points): 1 ≤ n ≤ 100 and 1 ≤ w_i, u, l ≤ 1000.
4. (15% of points): 1 ≤ n ≤ 10 000 and 1 ≤ w_i, u, l ≤ 10 000.
5. (23% of points): 1 ≤ n ≤ 10 000 and 1 ≤ w_i, u, l ≤ 500 000.
6. (31% of points): 1 ≤ n ≤ 200 000 and 1 ≤ w_i, u, l ≤ 2³¹.

All Submissions
Best Solutions

Point Value: 10 (partial)
Time Limit: 2.00s
Memory Limit: 2048M
Added: Aug 10, 2017

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)