Back
Close
  • 12

Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

Statement

 Goal

There is an array of items of various weights.
There is a number of identical bins. The bins are large enough to hold any combinations of items.

Instead of throwing all items into one bin, the requirement is to meticulously distribute the weights of the items into the given bins evenly.

After loading, all the bins should have the same weight. No one bin is heavier or lighter than the others.

Each item must be placed in exactly one bin. Items cannot be split into parts.

Mathematicians described bin packing as an NP-hard problem. To mitigate the difficulty, you do not need to tell how the items should be distributed. You just need to tell whether "even distribution" is achievable.
Input
There are multiple test cases in each test set.

Line 1: an integer n for the number of test cases.
Following n lines: each line is an independent test case, having space-separated integers
b m w1 w2 w3 ... wm

b is the number of bins for items to fill in,
m is the number of items to pack into bins,
followed by m integers for the weights of every item.
Output
n lines: for each test case, write a line either yes or no.
Write yes if all the items can be evenly distributed by weight among all the bins. Write no if it is impossible.
Constraints
1 ≤ n ≤ 100
1 ≤ b ≤ 6
1 ≤ m ≤ 20
1 ≤ w1 w2 w3 ... wm ≤ 1000
Example
Input
12
1 6 1 2 3 4 5 6
2 2 3 3
2 5 50 10 20 20 20
3 6 100 110 120 130 140 150
4 5 100 50 100 100 50
5 11 2 5 17 8 13 7 7 2 3 17 4
2 5 36 22 27 38 37
3 6 10 22 19 25 15 2
4 9 18 34 20 33 39 27 28 19 2
5 8 21 28 31 38 31 22 36 3
3 13 101 100 11 205 36 65 29 95 68 168 145 39 25
4 15 17 52 43 41 201 234 59 32 296 26 38 29 152 383 311
Output
yes
yes
yes
yes
yes
yes
no
no
no
no
no
no

A higher resolution is required to access the IDE