2770: T4-合法哈夫曼
内存限制：512 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
33DAI 最近做洛谷的 CSP-J 第一轮模拟赛时看到了下面这道题目。
假设有一组字符 `{g,h,i,j,k,l}`，它们对应的频率分别为 $8\%,14\%,17\%,20\%,23\%,18\%$。
请问以下哪个选项是字符 `g,h,i,j,k,l` 分别对应的一组哈夫曼编码？（ ）
- A. `g: 1100, h: 1101, i: 111, l: 10, k: 00, j: 01`
- B. `g: 0000, h: 001, i: 010, l: 011, k: 10, j: 11`
- C. `g: 111, h: 110, i: 101, l: 100, k: 01, j: 00`
- D. `g: 110, h: 111, i: 101, l: 100, k: 0, j: 01`
33DAI 发现直接哈夫曼树上构建的话，怎么都得不到某个选项。然后才学到了原来哈夫曼编码只需要保证长度没问题，且任意一个编码都不是其他编码的前缀即可。感谢洛谷带来的小知识。
## 题目描述
有 $n$ 个单词，编号从 $1\sim n$。第 $i$ 个单词的出现的次数为 $a_i$。
33DAI 对这些单词进行了二进制编码，第 $i$ 个单词编码后的二进制数用一个字符串 $s_i$ 表示。
请你判断 33DAI 的编码是不是这个出现次数下合法的哈夫曼编码。
- 如果是，输出 `Yes`，并计算出按照这个编码的文章总长度（二进制位数）。
- 否则，输出 `No`，并给出一组满足要求的哈夫曼编码。
**注意：本题中只要保证了在该二进制编码下，文章总长度能达到最短；且任意一个编码都不是其他编码的前缀；就认为是一个合法的哈夫曼编码。**
假设有一组字符 `{g,h,i,j,k,l}`，它们对应的频率分别为 $8\%,14\%,17\%,20\%,23\%,18\%$。
请问以下哪个选项是字符 `g,h,i,j,k,l` 分别对应的一组哈夫曼编码？（ ）
- A. `g: 1100, h: 1101, i: 111, l: 10, k: 00, j: 01`
- B. `g: 0000, h: 001, i: 010, l: 011, k: 10, j: 11`
- C. `g: 111, h: 110, i: 101, l: 100, k: 01, j: 00`
- D. `g: 110, h: 111, i: 101, l: 100, k: 0, j: 01`
33DAI 发现直接哈夫曼树上构建的话，怎么都得不到某个选项。然后才学到了原来哈夫曼编码只需要保证长度没问题，且任意一个编码都不是其他编码的前缀即可。感谢洛谷带来的小知识。
## 题目描述
有 $n$ 个单词，编号从 $1\sim n$。第 $i$ 个单词的出现的次数为 $a_i$。
33DAI 对这些单词进行了二进制编码，第 $i$ 个单词编码后的二进制数用一个字符串 $s_i$ 表示。
请你判断 33DAI 的编码是不是这个出现次数下合法的哈夫曼编码。
- 如果是，输出 `Yes`，并计算出按照这个编码的文章总长度（二进制位数）。
- 否则，输出 `No`，并给出一组满足要求的哈夫曼编码。
**注意：本题中只要保证了在该二进制编码下，文章总长度能达到最短；且任意一个编码都不是其他编码的前缀；就认为是一个合法的哈夫曼编码。**
输入
第一行是 $n$。
第二行为空格隔开的 $a_1\sim a_n$
接下来 $n$ 行，第 $i$ 行为 $s_i$
第二行为空格隔开的 $a_1\sim a_n$
接下来 $n$ 行，第 $i$ 行为 $s_i$
输出
按题目要求输出：
- 如果输入的是哈夫曼编码，输出两行：
- 第一行为 `Yes`
- 第二行为这个编码下的文章总长度
- 如果输入的不是哈夫曼编码，输出 $n+1$ 行：
- 第一行为 `No`
- 接下来 $n$ 行第 $i$ 行为第 $i$ 个单词对应的哈夫曼编码。
- 如果有多种方案，输出任意一种即可。
- 如果输入的是哈夫曼编码，输出两行：
- 第一行为 `Yes`
- 第二行为这个编码下的文章总长度
- 如果输入的不是哈夫曼编码，输出 $n+1$ 行：
- 第一行为 `No`
- 接下来 $n$ 行第 $i$ 行为第 $i$ 个单词对应的哈夫曼编码。
- 如果有多种方案，输出任意一种即可。
样例输入 复制
6
8 14 17 20 23 18
111
110
101
00
01
100样例输出 复制
Yes
257提示
```input2
6
8 14 17 20 23 18
0000
001
010
11
10
011
```
```output2
No
111
110
101
00
01
100
```
```input3
1
99
0
```
```output3
Yes
99
```
## 数据规模与约定
对于 $100\%$ 的数据，$1 \le n \le 60$，$1\le a_i\le 1000$，$1\le |s_i|\le 100$。保证 $s_i$ 仅有字符 `0,1` 构成，$|s_i|$ 表示字符串 $s_i$ 的长度。
- 子任务 1（10 分）：保证 $n=1$。
- 子任务 2（20 分）：保证输入的编码是一套哈夫曼编码。
- 子任务 3（30 分）：保证输入的编码任意一个都不是其他的编码的前缀。
- 子任务 4（40 分）：没有特殊限制。
6
8 14 17 20 23 18
0000
001
010
11
10
011
```
```output2
No
111
110
101
00
01
100
```
```input3
1
99
0
```
```output3
Yes
99
```
## 数据规模与约定
对于 $100\%$ 的数据，$1 \le n \le 60$，$1\le a_i\le 1000$，$1\le |s_i|\le 100$。保证 $s_i$ 仅有字符 `0,1` 构成，$|s_i|$ 表示字符串 $s_i$ 的长度。
- 子任务 1（10 分）：保证 $n=1$。
- 子任务 2（20 分）：保证输入的编码是一套哈夫曼编码。
- 子任务 3（30 分）：保证输入的编码任意一个都不是其他的编码的前缀。
- 子任务 4（40 分）：没有特殊限制。