#P18216. The Devil
The Devil
The Devil
缩写可以让表达变得简洁,但不同事物使用相同缩写会产生混淆。例如,China Collegiate Programming Contest、China Car Performance Challenge 和 Competition and Consumer Protection Commission 都可以缩写为 CCPC。
现在有 个短语,每个短语由若干个只含英文字母的单词组成。一个短语的缩写按如下方式构造:
- 对短语中的每个单词,分别选择它的一个非空前缀;
- 按原单词顺序,将选出的所有前缀直接拼接起来,得到一个不含空格的字符串。
例如,ChCoPrCo 和 CCPContest 都是 China Collegiate Programming Contest 的合法缩写,CCCP 和 CCPiC 则不是。
每个短语的选择彼此独立。即使某个单词出现在多个短语中,也不要求它在不同短语里选择相同的前缀。大小写字母视为不同字符。
请为这 个短语各选择一个缩写,使所有缩写字符串两两不同,并使它们的长度总和最小。
输入格式
第一行包含一个整数 ,表示短语数。
接下来 行,每行包含一个非空短语。短语中的相邻单词用一个空格分隔。
输出格式
如果不存在满足要求的方案,输出一行 no solution。
否则输出 行,第 行包含第 个输入短语所选的缩写。所有缩写必须合法、两两不同,且总长度达到最小值。若有多个最优方案,输出任意一个。
数据范围
- ;
- 每个短语包含 到 个单词;
- 每个单词包含 到 个大写或小写英文字母;
- 保证输入的短语两两不同。
样例 1
5
automated teller machine
active teller machine
active trouble maker
always telling misinformation
American Teller Machinery
atm
atma
actm
atem
ATM
样例 2
5
Forest Conservation Committee Forum
Fuming Corruption Collusion Federation
Fulsome Cash Concealment Foundation
Funky Crony Capitalism Facilitator
Funny Cocky Cocky Funny
FCCF
FCoCF
FuCCF
FCCFa
FCCFu
样例 3
3
A AA
AA A
A A A
no solution