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

View as PDF

Points: 15 (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 , where and 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 molecules with weights . The detection is successful if there is a set of distinct indices such that .

Due to specifics of the machine, the gap between and is guaranteed to be greater than or equal to the weight gap between the heaviest and the lightest molecule. Formally, , where and .

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 of input will contain three space-separated integers , , and , respectively representing the number of elements in (i.e, the number of molecules), and the endpoints of the detection range.
Line of input will contain , an array of length . The space-separated integers represent the weights of the molecules.

#### Output Specification

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

#### Sample Input 1

4 15 17
6 8 8 7

#### Sample Output 1

2
1 3

#### Explanation for Sample Output 1

In this example we have four molecules with weights , , and . The machine can detect subsets of molecules with total weight between and , inclusive. Note, that . The total weight of molecules and is , so the program can output [1, 3]. Other possible correct answers are [1, 2] and [2, 3] .

#### Sample Input 2

4 14 15
5 5 6 6

#### Sample Output 2

0

#### Explanation for Sample Output 2

In this example we have four molecules with weights , , and , and we are looking for a subset of them with total weight between and , inclusive. Again, note that . There is no subset of molecules with total weight between and so the program should output 0.

#### Sample Input 3

4 10 20
15 17 16 18

#### Sample Output 3

1
0

#### Explanation for Sample Output 3

In this example we have four molecules with weights , , and , and we are looking for a subset of them with total weight between and , inclusive. Again, note that . Any subset consisting of exactly one element has total weight between and , so the possible correct answers are: , ,  and .

#### Subtasks

1. (9 points): , all are equal.
2. (10 points): and .
3. (12 points): and .
4. (15 points): and .
5. (23 points): and .
6. (31 points): and .

## Comments

There are no comments at the moment.