
ZOJ Problem Set  3931
Huffman Code is a commonly used optimal prefix code. Here is a simple introduction to Huffman Coding from wikipedia.
For example, one day Edward wanted to send a string "aeaaaageqqqq" to his best friend Min as a gift. There are four symbols 'a', 'e', 'g', 'q' and so their weights are 5, 2, 1, 4. Firstly Edward merged the two symbols 'e' and 'g' with lowest weights and get a node with weight of 1 + 2 = 3. Then Edward merged two nodes of weight 3 and 4 and get a node with weight 3 + 4 = 7. Finally Edward merged the last two nodes. If we distribute the prefix '0' to the smaller node, Edward can get the code of four symbols '0', '101', '100', '11'. If we know the number of occurrences of each character in some content, can we compress it using Huffman Code and the number of '0's is exactly E? More precisely, let the number of occurrences of the ith character be F_{i} and the number of '0's in its huffman code be C_{i}, we want to know whether there exists a specific huffman code satisfying that the sum of F_{i} * C_{i} is equal to E. InputThere are multiple test cases. The first line of input is an integer T indicates the number of test cases. For each test case: The first line of each case contains a positive integer S (2 ≤ S ≤ 128), indicates the number of different symbols. The second line contains exactly S integers F_{i} (1 ≤ F_{i} ≤ 1000), indicates the number of occurrence of each symbol. The third line contains a nonnegative integer E (0 ≤ E ≤ 10^{8}), indicates the expected number of '0's. Output
For each case, please output "Yes" if it can be satisfied and "No" in otherwise. Sample Input3 2 1 3 2 2 1 3 3 4 5 2 1 4 11 Sample OutputNo Yes Yes HintThe possible huffman codes for examples:
Author: ZHAO, Yueqi Source: The 16th Zhejiang University Programming Contest 