History of OI -> II OI 1994/1995 -> Problems

 News About Olympic History of OI XVII OI 2009/2010 XVI OI 2008/2009 XV OI 2007/2008 XIV OI 2006/2007 XIII OI 2005/2006 XII OI 2004/2005 XI OI 2003/2004 X OI 2002/2003 IX OI 2001/2002 VIII OI 2000/2001 VII OI 1999/2000 VI OI 1998/1999 V OI 1997/1998 IV OI 1996/1997 III OI 1995/1996 II OI 1994/1995 Stage III - results Stage I - results Problems I OI 1993/1994 OI books National team Olympic camps Photo gallery Links SIO MAIN
Niebieskie ksi.eczki

The Concatenation of Words

 III stage contest

We are given a word w being a pattern and a finite sequence of nonempty words C = (w1, ..., wk). In the sequence C one should indicate words which form the pattern when concatenated in the same order as they appear in the sequence C. The answer is an increasing sequence of numbers of words of the given sequence C, which form the pattern after concatenation. The pattern w and each word in the sequence C consist of at most 150 small letters of English alphabet from 'a' to 'z' and contain no diacritics. The number of words in the sequence is positive and not greater then 200.

### Example

The pattern rytter can be formed from the words of the sequence C = (ry, r, yt, y, tt, t, e, te, r, er) choosing successively and concatenating the words numbered (2, 4, 5, 7, 9). The choice (1, 5, 10) is another way to obtain the same pattern.

Write a program that:
• reads from the text file SLO.IN the following data: the pattern w, the number of words in the sequence C, and successive words of the sequence,
• if there is no way to form the pattern w from the words of the sequence C according to the rules given above, then it writes one word NIE ("no") in the file SLO.OUT,
• if there exist solutions and their number is less then 1000000, then it writes in the text file SLO.OUT the number of solutions, and then one of the solutions to the task,
• if there are more solutions then 999999, then it writes in the file SLO.OUT the number 1000000, and then one of the solutions to the task.

### Input

• In the first line of the file SLO.IN there is one word composed of at most 150 small letters of English alphabet. That is the pattern w.
• In the second line there is a positive integer k <= 200. That is the number of words of the sequence C.
• In the consecutive k lines there are successive nonempty words composing the sequence C, each word is written in a separate line and consists of at most 150 small letters of English alphabet. The first letter of a word is always the first character in the corresponding line, and just after the last letter there is the end of the line.

### Output

In the file SLO.OUT one should write:
• either one word NIE, when it is impossible to form the pattern from the words of the sequence C meeting the rules of the task,
• or in the first line - one number being either the number of solutions to the task or 1000000;
in the following lines - an increasing sequence of numbers of the chosen words from the sequence C which after concatenation form the pattern - each number in a separate line.

### Example

For the file SLO.IN:
```rytter
10
ry
r
yt
y
tt
t
e
te
r
er
```
the file SLO.OUT may contain:
```9
2
4
5
7
9
```

Your program should look for the file SLO.IN in the current directory and create the file SLO.OUT also in the current directory. The source file containing the program written by you should be named SLO.???, where ??? are substituted by at most three-letter abbreviation of the programming language used. The same program in an executable form should be written in a file SLO.EXE.

Print friendly version