1683: 【USACO】Superwords

时间限制: 1.000 Sec  内存限制: 64 MB
提交: 20  解决: 2
[提交] [状态] [报告] [命题人:]


The cows are playing dictionary games again; there's not much else to do while chewing one's cud. The new game is a simple one but they need to verify their answers. Given a list of N (1 <= N <= 100) words, what is the smallest "superword" that contains all of them, in order, as subwords? Consider an example using three words: 'big', 'green', and 'engine'. To make a "superword" (which, regrettably, rarely appears in the dictionary), one combines them carefully to yield: 'bigreengine'. Words appear sequentially in a superword when the first letter of a constituent word appears strictly later in the superword than the first letter of the previous word and the last letter of that word appears strictly later in the superword than the last letter of the previous word. Here are some two word examples: sin in -> sinin sin si -> sinsi sin int -> sint Your task is to find superwords.


* Line 1: A single integer, N * Lines 2..N+1: Each line contains a single word that contains only lower case letters ('a'..'z'). No word is longer than 75 characters.


A single line that contains the "superword".


输入  复制
3 big green engine
输出  复制