|Online Judge||Problem Set||Authors||Online Contests||User|
A double linear crossword of length L is a string of L lowercase alphabetic characters arranged in a line in such a way that there are at least two methods (so called decompositions) to split this string into the words from the given list. Look at the example for L=17:
The words were taken from the following list: all, an, and, are, area, as, ask, at, data, last, or, read, real, task.
The words from the first decomposition may not appear in the second one and vice versa. In addition, no word can be repeated in any decomposition.
No word in one decomposition can end in the same place of the string where a word in the other composition ends, except, naturally, for the end of the string (otherwise the crossword can be separated into two independent crosswords). One of the compositions may consist of a single word.
You should write a program to construct the first, in lexicographic order, double linear crossword of length L for a given list of words.
Strings are arranged in the lexicographic order with respect of the following rules:
The first line of the input file consists of the single integer number L (4<=L<=50) denoting the desired crossword length. The second line consists of the single positive integer N (at most 1000) indicating the number of words in the list. Each of the followings N lines consists of a string of 20 or less (but at least 2) latin lowercase alphabetic characters. The words in the list are arranged in lexicographic order and no word is repeated.
For the given input data set your program should write to the output file the first, in lexicographic order, double linear crossword with the given length. If it is impossible for the given input file to construct a double linear crossword with the given length, the program should write only the message "NO SOLUTION" (without the quotation marks).
17 19 all an and area as ask at data do for last of or ort read real task to tor
[Submit] [Go Back] [Status] [Discuss]
Home Page Go Back To top
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator