Polish version    English version  
  History of OI -> II OI 1994/1995 -> Problems

 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
I OI 1993/1994
 OI books
 National team
 Olympic camps
 Photo gallery
Niebieskie ksi.eczki
II Olympiad in Informatics 1994/1995

Task: SLO
Author: Wojciech Rytter
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.


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.


  • 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.


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.


For the file SLO.IN:
the file SLO.OUT may contain:

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