#6036. 「雅礼集训 2017 Day4」编码

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

原题:NEERC 2016 B. Binary Code

Bob 最新学习了一下二进制前缀编码的那一套理论。二进制编码是指一个由 n 个互不相同的二进制串 s_1, s_2, \ldots, s_n 构成的集合。而如果一套编码理论满足,对于任意的 i \neq j s_i 不是 s_j 的前缀,那么我们称它为前缀编码。

Bob 发现了一张上面写有 n 行二进制编码的纸,但这张纸年代久远,有些字迹已经模糊不清。幸运的是,每一行至多只会有一个模糊的字符。

Bob 想知道这 n 行二进制编码是否有可能是一个前缀编码?

输入格式

第一行一个整数 n ,表示编码的大小。
接下来 n 行,每行一个由 01? 组成的字符串。保证每一行至多有一个 ?

输出格式

如果这 n 个二进制编码可能是前缀编码,输出 YES,否则输出 NO

样例

样例输入 1

4
00?
0?00
?1
1?0

样例输出 1

YES

样例解释 1

一组可能的解为:

000
0100
11
100

样例输入 2

3
0100
01?0
01?0

样例输出 2

NO

数据范围与提示

本题采用捆绑测试。
你需要通过一个子任务内的所有测试点才能得到该子任务的分数。

子任务 分值 n 字符串总长
1 20 \leq 10 \leq 1000
2 30 \leq 1000 \leq 500000
3 50 \leq 500000