最新消息:380元/半年,推荐全网最具性价比的一站式编程学习平台码丁实验室

信息学奥赛题库- 最小字典序

C++ 少儿编程 1403浏览 0评论

友情提示:380元/半年,儿童学编程,就上码丁实验室

【题目描述】

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

一个合法的字符串要满足以下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$。

您必须 登录 才能发表评论!