407354: GYM102770 B Bin Packing Problem

Lzw is having the Operations Research class now. Today the teacher is talking about the bin packing problem and some approximation algorithms to solve it.

In the bin packing problem, items of different volumes must be packed into a finite number of bins with a fixed capacity $$$C$$$ in a way that minimizes the number of bins used. In computational complexity theory, it is a combinatorial NP-hard problem.

There are two classical approximation algorithms.

• First Fit Algorithm. Consider the items in input order and maintain a list of bins, initially empty. In each step, it attempts to place the current item in the first bin in the list that can accommodate the item. If no suitable bin is found, it appends a new bin at the end of the list and puts the item into the new bin.
• Best Fit Algorithm. Consider the items in input order and maintain a list of bins, initially empty. In each step, it attempts to place the current item in the best bin that can accommodate the item. "Best" means that if there are more than one bins that can accommodate the item, the bin with the least remaining space is chosen. If no suitable bin is found, a new bin is added and the item is put into the new bin.

Please help Lzw implement these two algorithms and find out how many bins will each algorithm use.

The input contains multiple cases. The first line of the input contains a single positive integer $$$T$$$, the number of cases.

For each case, the first line of the input contains two integers $$$n,C\ (1 \le n \le 10^6,\ 1 \le C \le 10^9)$$$, the number of items and the capacity of each bin. The second line contains $$$n$$$ integers, where the $$$i$$$-th ($$$1 \le i \le n$$$) integer $$$a_i\ (1 \le a_i \le C)$$$ denotes the volume of the $$$i$$$-th item.

It is guaranteed that the sum of $$$n$$$ over all cases doesn't exceed $$$10^6$$$.

For each case, print a single line containing two integers, denoting the number of bins used by the First Fit and the Best Fit algorithm, respectively.

2
2 2
1 1
5 10
5 8 2 5 9

1 1
4 3