Repovive
  • Dashboard
  • Ranking
  • Submissions
  • Discussion
  1. Contests
  2. Weekly Challenge 1: Approximation
  3. W1D1B

My submissions

/
/
/
/

Announcements

My submissions

/
/
/
/

Announcements

Solve
Author

W1D1B. Full Enough (Hard Version)

2 pts·1s·256 MB

Constraints

Input

Output

Samples

Input
1
8 100
45 45 60 40 30 20 15 5
Explanation
Output
2
1 2

You are given nnn stones. The weight of stone iii is wiw_iwi​.

You have a bag with capacity WWW. You may choose any subset of stones whose total weight is at most WWW.

It is guaranteed that there exists a non-empty subset of stones whose total weight is exactly WWW.

You do not need to find such an exact subset. You only need to choose a subset whose total weight is at least 90%90\%90% of WWW and at most WWW.

  • 1≤t≤51 \le t \le 51≤t≤5
  • 1≤n≤7501 \le n \le 7501≤n≤750
  • The sum of nnn over all test cases is at most 750750750
  • 1≤W≤10121 \le W \le 10^{12}1≤W≤1012
  • 1≤wi≤W1 \le w_i \le W1≤wi​≤W
  • There exists a non-empty subset with total weight exactly WWW

The input is given in the following format:

ttt nWw1w2⋯wn}×t\left. \begin{array}{l} n \quad W \\ w_1 \quad w_2 \quad \cdots \quad w_n \end{array} \right\} \times tnWw1​w2​⋯wn​​}×t

For each test case, first output an integer kkk, the number of chosen stones.

Then output kkk distinct integers i1,i2,…,iki_1,i_2,\ldots,i_ki1​,i2​,…,ik​, the indices of the chosen stones.

The total weight of the chosen stones must be at most WWW and at least 90%90\%90% of WWW.

The output format is:

ki1i2⋯ik}×t\left. \begin{array}{l} k \\ i_1 \quad i_2 \quad \cdots \quad i_k \end{array} \right\} \times tki1​i2​⋯ik​​}×t

If k=0k=0k=0, the second line may be empty.

The chosen stones have total weight 45+45=9045+45=9045+45=90.

This does not fill the bag exactly, but it is still valid because 909090 is exactly 90%90\%90% of 100100100 and does not exceed the capacity.