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 i-th character be Fi and the number of '0's in its huffman code be Ci, we want to know whether there exists a specific huffman code satisfying that the sum of Fi * Ci is equal to E.
There 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 Fi (1 ≤ Fi ≤ 1000), indicates the number of occurrence of each symbol.
The third line contains a non-negative integer E (0 ≤ E ≤ 108), indicates the expected number of '0's.
For each case, please output "Yes" if it can be satisfied and "No" in otherwise.
3 2 1 3 2 2 1 3 3 4 5 2 1 4 11
No Yes Yes
The possible huffman codes for examples:
Author: ZHAO, Yueqi
Source: The 16th Zhejiang University Programming Contest