CF490E.Restoring Increasing Sequence

普及+/提高

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

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

题目描述

Peter wrote on the board a strictly increasing sequence of positive integers _a_1, _a_2, ..., a__n. Then Vasil replaced some digits in the numbers of this sequence by question marks. Thus, each question mark corresponds to exactly one lost digit.

Restore the the original sequence knowing digits remaining on the board.

彼得在黑板上写下一个严格递增的正整数序列 a1, a2, …, ana_1,\,a_2,\,\dots,\,a_n。随后,瓦西里将该序列中某些数字的若干数位替换为了问号。每个问号恰好对应一个丢失的数位。

请根据黑板上剩余的数字,还原出原始序列。

输入格式

The first line of the input contains integer n (1 ≤ n ≤ 105) — the length of the sequence. Next n lines contain one element of the sequence each. Each element consists only of digits and question marks. No element starts from digit 0. Each element has length from 1 to 8 characters, inclusive.

输入的第一行包含一个整数 nn(1≤n≤1051 \leq n \leq 10^5)—— 表示序列的长度。接下来的 nn 行每行包含序列中的一个元素。每个元素仅由数字和问号组成,且不以数字 00 开头。每个元素的长度为 11 到 88 个字符(含端点)。

输出格式

If the answer exists, print in the first line "YES" (without the quotes). Next n lines must contain the sequence of positive integers — a possible variant of Peter's sequence. The found sequence must be strictly increasing, it must be transformed from the given one by replacing each question mark by a single digit. All numbers on the resulting sequence must be written without leading zeroes. If there are multiple solutions, print any of them.

If there is no answer, print a single line "NO" (without the quotes).

如果答案存在,在第一行输出“YES”(不带引号)。接下来的 nn 行必须包含一个正整数序列——即彼得序列的一种可能方案。所找到的序列必须严格递增,且必须通过对给定序列中每个问号(?)替换为一个单独数字而得到。最终序列中的所有数字均不得含有前导零。若存在多个解,输出任意一个即可。

若无解,则仅输出一行“NO”(不带引号)。

输入输出样例

  • 输入#1

    3
    ?
    18
    1?

    输出#1

    YES
    1
    18
    19
  • 输入#2

    2
    ??
    ?

    输出#2

    NO
  • 输入#3

    5
    12224
    12??5
    12226
    ?0000
    ?00000

    输出#3

    YES
    12224
    12225
    12226
    20000
    100000

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

首页