Lunch Boxes

Masao and Naini, both Shinchan friends, are playing "home-home". But wait, they both forgot to bring any lunch box. Being a good partner Naini cannot allow Masao to go office without luch box. So she asked Masao to buy some.

Naini has N food items to be packed in the lunch box and maximum weight each lunch box can hold is W units. Let the weight of N items be w_0, w_1, ..., w_(N-1) units and each item's weight lies between 1 and W (inclusive). Find the arrangement so that the number of lunch box required to pack all food items is minimised.

Let's say Masao bought K lunch box (b_0, b_1,..., b_(K-1)) for packing N items. For each i'th box in [0, K-1], print the indices of food items, j in [0, N-1], which is placed in it. Each food item must be placed in only one box.

Help Masao in finding K and respective placement of food items in these boxes.

Constraints
1 <= N <= 10^5 1 <= W <= 10^5 1 <= w_i <= W

Input
First line of input contains two space separated integers, N W, numbers of food items to be packed and maximum weight each lunch box can hold.
Next line contains N space separated integers, w_0, w_1...w_(N-1), weights of 0'th item, 1'st item, ..., (N-1)'th item.

Output
In first line print an integer, K, numbers of lunch box required for packing all the food items. Then print K lines. Each of these line represents the content of a box. Each of these lines contains a number M (1 <= M), number of food items to be placed in current box followed by M space separated indexes of food items.

Scoring
Maximum number of lunch box required is N. The score will be equal to (N - K) / N * [Score of problem]

---

Sample Input

6 6
1 2 4 3 5 3

Sample Output

4
3 0 1 5
1 3
1 2
1 4

Explanation

In the give sample input/output, Naini used 4 boxes. 1st box contains 3 items, w_0 = 1, w_1 = 2, w_5 = 3. 2nd box contains 1 item, w_3 = 3. Similarly 3rd and 4th box contains 1 item each, w_2 = 4 and w_4 = 5, respectively.
Score for Input #1: 66.67.
Similarly, consider the following example.
Sample Input #2: 6 6 1 2 4 3 5 3
Sample Output #2: 3 2 0 4 2 1 2 2 5 3
Score for Input #2: 100.00
Naini used 3 boxes. 1st box contains 2 items, w_0 = 1, w_4 = 5. 2nd box contains 2 items, w_1 = 2, w_2 = 4. 3rd box also contains 2 items, w_5 = 3, w_3 = 3.

---

Time Limit: 6 sec(s) for all input files combined.

Memory Limit: 256 MB

Source Limit: 1024 KB 

 

Code: 

 

/*
 * uncomment this if you want to read input.*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;


class TestClass {
    static int[] w;
    public static void main(String args[] ) throws Exception {
       
        BufferedReader br =
            new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        String[] nums = line.split(" +");
        int N = Integer.parseInt(nums[0]);
        int W = Integer.parseInt(nums[1]);
        w = new int[N];
        String line2 = br.readLine();
        String[] wis = line2.split(" +");


        for (int i = 0; i < N; i++) {
            w[i] = Integer.parseInt(wis[i]);

        }

        Integer[] index = new Integer[N];
        for (int t = 0; t < N; t++) {
            index[t] = t;
        }
        Comparator<Integer> com = new Comparator<Integer>() {

            public int compare(Integer o1, Integer o2) {
                return w[o1] - w[o2];
            }
        };
        Arrays.sort(index, com);

        ArrayList<ArrayList<Integer>> lists =
            new ArrayList<ArrayList<Integer>>();

        int start = 0;
        int end = N - 1;
        while (start <= end) {
            ArrayList<Integer> list = new ArrayList<Integer>();

            int cap = W;
            while (end >= 0 && w[index[end]] <= cap) {
                list.add(index[end]);
                cap -= w[index[end]];
                end--;
            }
            while (start <= end && start <= N - 1 && w[index[start]] <= cap) {
                list.add(index[start]);
                cap -= w[index[start]];
                start++;
            }
            lists.add(list);
            if(start==end){
                list = new ArrayList<Integer>();
                list.add(index[start]);
                lists.add(list);
                break;
            }
           
           
        }
        System.out.println(lists.size());
        int lsize = lists.size();
        for (int i = 0; i < lsize; i++) {
            int asize = lists.get(i).size();
            System.out.print(asize + " ");
            for (int j = 0; j < asize; j++) {
                System.out.print(lists.get(i).get(j) + " ");
            }
            System.out.println();
        }
     
    }
}