IOI '16 P1 - Detecting Molecules (Standard I/O)

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 0.6s
Memory limit: 256M

Problem type

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,,wn1. The detection is successful if there is a set of distinct indices I={i0,,im1} such that lwi0++wim1u.

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, ulwmaxwmin, where wmax=max(w0,,wn1) and wmin=min(w0,,wn1).

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.

Input Specification

The input will be given in the following format:

Line 1 of input will contain three space-separated integers n, l, and u, respectively representing the number of elements in w (i.e., the number of molecules), and the endpoints of the detection range.
Line 2 of input will contain w, an array of length n. The space-separated integers w[0],w[1],,w[n1] represent the weights of the molecules.

Output Specification

You should output two lines. On the first line, a single integer m, the size of the required subset, or 0, if no such subset can be found.
The second line should contain m space separated integers: i1,i2,,im, the indices of the required subset.

Sample Input 1

Copy
4 15 17
6 8 8 7

Sample Output 1

Copy
2
1 3

Explanation for Sample Output 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 171586. The total weight of molecules 1 and 3 is w1+w3=8+7=15, so the program can output [1, 3]. Other possible correct answers are [1, 2] (w1+w2=8+8=16) and [2, 3] (w2+w3=8+7=15).

Sample Input 2

Copy
4 14 15
5 5 6 6

Sample Output 2

Copy
0

Explanation for Sample Output 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 151465. There is no subset of molecules with total weight between 14 and 15 so the program should output 0.

Sample Input 3

Copy
4 10 20
15 17 16 18

Sample Output 3

Copy
1
0

Explanation for Sample Output 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 20101815. 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 points): 1n100,1wi100,1u,l1000, all wi are equal.
  2. (10 points): 1n100,1wi,u,l1000 and max(w0,,wn1)min(w0,,wn1)1.
  3. (12 points): 1n100 and 1wi,u,l1000.
  4. (15 points): 1n10000 and 1wi,u,l10000.
  5. (23 points): 1n10000 and 1wi,u,l500000.
  6. (31 points): 1n200000 and 1wi,u,l<231.

Comments

There are no comments at the moment.