Subtask 1

This subtask is intended to reward brute force solutions or inefficient implementations of the intended full solution.

Subtask 2

This subtask is intended to reward incorrect greedy approaches. For example, sort the ~M~ pieces of currency from ~x_i~ lowest to greatest, and then for each bag, greedily pick the coin with the lowest ~x_i~ that can fit using binary search, and repeat for each bag.

Time complexity: ~\mathcal{O}(M \log M)~

Subtask 3

The intended solution is to merge coins of even denomination into larger coins until there is either ~0~ or ~1~ of each coin, and merge coins of odd denomination until there is at most ~x_i - 1~ of each coin. Note that after merging, all coins of denomination ~1~ and ~2~ can be placed into separate groups.

Consider the coins ~\frac{1}{2k}~ and ~\frac{1}{2k-1}~ for ~k > 1~. Notice that after the merging of coins, the sum is at most ~\frac{1}{2k} + \frac{2k-2}{2k-1} < 1~. Therefore, form as many possible remaining groups using this observation.

Finally, the rest of the coins can be added greedily to whichever group can hold it without exceeding a sum of ~1~ due to the fact that ~\sum{\frac{1}{x_i}} \leq N-\frac{1}{2}~. The proof is left as an exercise to the reader.

Time complexity: ~\mathcal{O}(M \log \max(x_i))~