1369: ShacozzZ的老鹰捉小鸡
Memory Limit:128 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:9
Solved:5
Description
某天,ShacozzZ决定和队友玩老鹰捉小鸡。
经过几轮游戏下来,ShacozzZ发现了一个神奇的规律:所有组成小鸡的队友,当他们的名字的首字母按照队伍的顺序排列时,字典序越小队伍的稳定性就越高。但是由于大家不愿意花太多的精力放在调整队伍顺序上,所以ShacozzZ每一次只能指定第一个队友走到队伍的末尾。请问队伍稳定性最高时,名字首字母组成的字符串是什么?
更正式的说,现在有 $n$ 个队友,第 $i$ 个队友的名字是 $s_i$ ,队伍一开始是 $t=s_1[1]s_2[1]s_3[1]...s_n[1]$ ,ShacozzZ第一次操作可以使队列变为 $t=s_2[1]s_3[1]...s_n[1]s_1[1]$ ,第二次使队列变为 $t=s_3[1]...s_n[1]s_1[1]s_2[1]$ ,以此类推。请通过若干次操作使 $t$ 的字典序最小,并输出 $t$。
两个字符串 $s$ 和 $t$ ,当 $s[i]<t[i]$ 且 $\forall j<i,s[j]=t[j]$ 时,或者 $|s|<|t|$ 且 $\forall 1 \leq i \leq |s|,s[i]=t[i]$ 时,称$s$ 的字典序小于 $t$ 。例如 $abdc$ 的字典序小于 $abfa$ , $abc$ 的字典序小于 $abcaaa$
经过几轮游戏下来,ShacozzZ发现了一个神奇的规律:所有组成小鸡的队友,当他们的名字的首字母按照队伍的顺序排列时,字典序越小队伍的稳定性就越高。但是由于大家不愿意花太多的精力放在调整队伍顺序上,所以ShacozzZ每一次只能指定第一个队友走到队伍的末尾。请问队伍稳定性最高时,名字首字母组成的字符串是什么?
更正式的说,现在有 $n$ 个队友,第 $i$ 个队友的名字是 $s_i$ ,队伍一开始是 $t=s_1[1]s_2[1]s_3[1]...s_n[1]$ ,ShacozzZ第一次操作可以使队列变为 $t=s_2[1]s_3[1]...s_n[1]s_1[1]$ ,第二次使队列变为 $t=s_3[1]...s_n[1]s_1[1]s_2[1]$ ,以此类推。请通过若干次操作使 $t$ 的字典序最小,并输出 $t$。
两个字符串 $s$ 和 $t$ ,当 $s[i]<t[i]$ 且 $\forall j<i,s[j]=t[j]$ 时,或者 $|s|<|t|$ 且 $\forall 1 \leq i \leq |s|,s[i]=t[i]$ 时,称$s$ 的字典序小于 $t$ 。例如 $abdc$ 的字典序小于 $abfa$ , $abc$ 的字典序小于 $abcaaa$
Input
第一行包含一个整数 $n(1 \leq n \leq 100)$ ,代表充当小鸡的队友。
接下来 $n$ 行,第 $i$ 行包含一个字符串 $s_i(1 \leq |s| \leq 100)$ ,代表初始位置为 $i$ 的队友的名字,保证字符串均为小写字符。
接下来 $n$ 行,第 $i$ 行包含一个字符串 $s_i(1 \leq |s| \leq 100)$ ,代表初始位置为 $i$ 的队友的名字,保证字符串均为小写字符。
Output
第一行包含一个字符串,即最后的队伍顺序中所有人首字母所构成的字符串
Sample Input Copy
3
shacozzz
expmin
chenbi
Sample Output Copy
cse
HINT
队伍只有 $sec$ , $ecs$ , $cse$ 三种情况,显然 $cse$ 字典序最小