Polish version    English version  
  History of OI -> III OI 1995/1996 -> 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
Stage III - results
Stage II - results
Stage I - results
Problems
II OI 1994/1995
I OI 1993/1994
 OI books
 National team
 Olympic camps
 Photo gallery
 Links
 SIO
 MAIN
Niebieskie ksi.eczki
III Olympiad in Informatics 1995/1996

Task: WYR
Author: Wojciech Rytter
Words equalizing

III stage contest  

There are given two words x, y and finite series of words (w1, w2, ... , wk).

An operation w * wi means a connection (concatenation) of word w with another word wi (1 <= i <= k), i.e. – in other words – is writing a word wi just after the word w. We want to verify if the words x and y can be equalized with words from the given series. The question is whether it is possible to extend the words x and y with words from the series in order to produce two identical words.

Example
The words abba and ab can be equalized with the words from the series: baaabad aa badccaa cc. In this purpose to the word abba we should add: aa and badccaa, and to the word ab - firstly baaabad, then cc, and eventually aa. In both cases we result in the same word: abbaaabadccaa.

Task

Write a program that:
  • Reads from the text file WYR.IN a length k of a given series of words, then descriptions of two words xand y as well as descriptions of the words from the series: (w1, w2, ... , wk),
  • Verifies whether the words x and y can be equalized with the words from the given series. If it is possible it finds the minimal number of operations *, which are necessary,
  • write this number in the text file WYR.OUT.

Input

  • In the first line of the textfile WYR.IN there is written a positive integer k <= 40. This is the length of the series (w1, w2, ... , wk).
  • In the second and the third line there are descriptions of the words x and y.
  • In the following k lines there are descriptions of the succeeding words in the series (w1, w2, ... , wk) – each description in a separate line
  • A description of the word consists of a natural number, which is the length of the word, and a word itself written as a series of characters. The number and the word are separated by a single space.
  • Each word consists only of small English letters from a to z and its length is not greater than 2000.
  • The sum of lengths of all given words is not greater than 5000.

Output

In the text file WYR.OUT there should be written:

  • One nonnegative integer, the minimal number of operations *, which are necessary to equalize given words x and y,
  • or the word NIE (no in Polish), if it is not possible to equalize the words

Examples

For the input file WYR.IN:
4
4 abba
2 ab
7 baaabad
2 aa
7 badccaa
2 cc

In the text file WYR.OUT there should be written one integer:
5

For the input file WYR.IN:
4
1 a
2 ab
2 bb
2 ab
2 ba
2 aa

In the text file WYR.OUT there should be written one word:
NIE

Your program should look for the file WYR.IN in the current directory and produce the output file WYR.OUT in the current directory too. The file containing the source code of your program should have a name WYR.???, whereas you should put three-letter abbreviation of the used programming language name instead of ???. The same program in executable form should be written in the file WYR.EXE




Print friendly version