IOI '95 - Eindhoven, Netherlands

Word Chains

A word consists of at least one and at most 75 lowercase letters (from `a' to `z'). A list of one or more words is called a chain when each word in that list, except the first, is obtained from the preceding word by appending one or more letters on the right. For instance, the list

i
in
int
integer

is a chain of four words, but the list

input
integer

is not a chain. Note that every list of one word is a chain.

Input Format

Your program is given a list of words containing at least one word and all of the words together have no more than 2,000,000 letters. The input is terminated with a line containing a single period (`.'). All other lines contain one word each. The list is sorted lexicographically using the standard alphabetical ordering (as in an English dictionary). There are no duplicate words in the list.

Output Format

The length of a chain is the number of words it contains. Your program should write to the output a longest chain of words taken from the input. Each word should be on a separate line.

If there is more than one chain of maximum length, your program should output only one of these chains. It does not matter which one.

Sample Input

i
if
in
input
int
integer
output
.

Sample Output

i
in
int
integer

All Submissions
Best Solutions

Point Value: 12
Time Limit: 1.00s
Memory Limit: 8M
Added: Apr 13, 2014

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

The input data for this problem contains a bunch of stray '\r' characters which may cause you grief if you're freading the input in bulk.

So um... the IOI '95 competition rules says that their environment consisted of Tulip Vision Lines with 75 MHz Pentium processors ([url]http://olympiads.win.tue.nl/ioi/ioi95/contest/c-rules.html[/url]). Upon doing some research, I found this: [url]http://www.cc-seller.de/CC-Archiv/bc-aktuell/gb-tulip/gb-tulip-12_95.html[/url]. If you Ctrl+F "Pentium / 75 MHz", you'll see that the model of this computer had 8MB of memory.

Which means that back in 1995 when this task was written, the author probably recognized the low memory limit to be a challenge in and of itself - which is why I think the memory limit for this problem should be lowered to 8MB to preserve the authenticity of older IOI's. Unfortunately this means that some current solutions will have to not pass.