III Olympiad in Informatics 1995/1996
|
Task: WYR
|
Author: Wojciech Rytter
|
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.
In the text file WYR.OUT there should be written:
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