1683: 【USACO】Superwords时间限制: 1 Sec 内存限制: 64 MB
提交: 9 解决: 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".