CF37C.Old Berland Language

普及+/提高

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Berland scientists know that the Old Berland language had exactly n words. Those words had lengths of _l_1, _l_2, ..., l__n letters. Every word consisted of two letters, 0 and 1. Ancient Berland people spoke quickly and didn’t make pauses between the words, but at the same time they could always understand each other perfectly. It was possible because no word was a prefix of another one. The prefix of a string is considered to be one of its substrings that starts from the initial symbol.

Help the scientists determine whether all the words of the Old Berland language can be reconstructed and if they can, output the words themselves.

伯兰德科学家们知道,古伯兰德语恰好包含 nn 个单词。这些单词的长度分别为 l1, l2, …, lnl_1,\,l_2,\,\dots,\,l_n 个字母。每个单词仅由两个字符 0 和 1 构成。古代伯兰德人说话很快,词与词之间不加停顿,但与此同时他们总能完美地相互理解。之所以可行,是因为没有任何一个单词是另一个单词的前缀。字符串的前缀定义为从其首字符开始的任意子串。

请帮助科学家判断:古伯兰德语的所有单词是否能够被唯一重构?若可以,请输出这些单词本身。

输入格式

The first line contains one integer N (1 ≤ N ≤ 1000) — the number of words in Old Berland language. The second line contains N space-separated integers — the lengths of these words. All the lengths are natural numbers not exceeding 1000.

第一行包含一个整数 NN(1≤N≤10001 \leq N \leq 1000)—— 古伯兰德语中单词的数量。
第二行包含 NN 个用空格分隔的整数——这些单词的长度。所有长度均为不超过 10001000 的正整数。

输出格式

If there’s no such set of words, in the single line output NO. Otherwise, in the first line output YES, and in the next N lines output the words themselves in the order their lengths were given in the input file. If the answer is not unique, output any.

如果不存在这样的单词集合,则在单独一行中输出 NO。否则,在第一行输出 YES,接下来的 N 行中按输入文件中给出的长度顺序输出这些单词。若答案不唯一,输出任意一个即可。

输入输出样例

  • 输入#1

    3
    1 2 3

    输出#1

    YES
    0
    10
    110
  • 输入#2

    3
    1 1 1

    输出#2

    NO

输入解题思路,AI测评打分。不知道怎么写?

首页