编程题

1682:最小字典序


时间限制: 1000 ms         内存限制: 131072 KB
提交数:338    通过数: 71

【题目描述】

给出一个只有数字、逗号和问号组成的字符串,其中问号表示这个字符未知,你需要尝试还原出这个字符串,使得这个字符串合法且字典序最小(逗号的字典序比数字小)。

一个合法的字符串要满足以下4个条件:

(1) 仅包含数字和逗号;

(2) 相邻数字用逗号隔开,但串首和串尾不能有逗号;

(3) 所有数字都是正整数,没有前导0;

(4) 数字序列严格递增。

【输入】

第一行一个正整数$T$,表示数据组数。

接下来$T$行,每行一个字符串$S$,表示需要还原的字符串。

【输出】

对于每组数据,输出还原后的串。如果无解,输出“$impossible$”(不含引号)。

【输入样例】

5
??
???
?????????,9
?,10,?????????????????,16,??
?2?5??7?,??

【输出样例】

10
1,2
1,2,3,4,5,9
impossible
12,50,70,71

【提示】

【数据规模与约定】

对于40%的数据,保证问号不超过$10$个。

对于100%的数据,$1≤T≤10,1≤len(S)≤50$。

查看答案
赣ICP备20007335号-2