CBOJ Winter Contest Problem 2 - Suitcase Packing
Bob is dreaming about going on vacation, but before he embarks on his journey, he must pack his bags!
Bob's airport enforces a weight limit of \(W\) kilograms for each suitcase. Bob can pack as many suitcases as he wants, as long as none of them hold items that exceed \(W\) kilograms when added up. As Bob's items are rather bulky, he can only pack a maximum of 2 things into 1 suitcase.
Given a list of \(N\) items Bob wishes to bring, find the minimum number of suitcases Bob needs to carry all his things, with each suitcase being within weight limit!
Note that Python users should submit their solution in PyPy over CPython.
The first line contains two integer \(N\) and \(W\) \((1 \le N \le 10^4, 1 \le W \le 10^9)\), representing the number of items Bob wants to bring and the airport's suitcase weight limit.
The next line contains \(N\) integers with values ranging from \(1\) to \(W\) inclusive, with the \(i\)-th element describing the \(i\)-th item's weight in kilograms.
Note that the weight limit will always be greater than or equal to the heaviest item Bob is planning to pack.
Output an integer, indicating the minimum number of suitcases Bob needs.
4 5 3 2 1 3
Bob can pair the items \((1, 3)\) and \((2, 3)\) together, forming suitcases with weights of 4kg and 5kg respectively.