Polish version    English version  
  O olimpiadzie -> Zadania


 Aktualności
 O olimpiadzie
O olimpiadzie
Zadania
I OI 1993/1994
II OI 1994/1995
III OI 1995/1996
IV OI 1996/1997
V OI 1997/1998
VI OI 1998/1999
VII OI 1999/2000
VIII OI 2000/2001
IX OI 2001/2002
X OI 2002/2003
XI OI 2003/2004
XII OI 2004/2005
XIII OI 2005/2006
XIV OI 2006/2007
XV OI 2007/2008
Archiwum zadań
Ankieta OI
 Komitety
 XVIII OI 2010/2011
 Historia OI
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
III Olimpiada Informatyczna 1995/96

Zadanie: WYR
Autor: Wojciech Rytter
Wyrównywanie słów

Zawody III stopnia  
Plik źródłowy: WYR.??? (np. pas, c, cpp)
Plik wykonywalny: WYR.exe
Plik wejściowy: WYR.in
Plik wyjściowy: WYR.out

 

Dane są dwa słowa x i y oraz skończony ciąg słów (w1, w2, ... , wk).

Operacja w * wi polega na połączeniu (konkatenacji) słowa w ze słowem wi (1 <= i <= k), czyli - mówiąc inaczej - na dopisaniu do słowa w, z prawej jego strony, słowa wi.

Chcemy sprawdzić, czy słowa x i y można wyrównać za pomocą słów z danego ciągu. To znaczy, czy można po wykonaniu skończonej liczby operacji dopisywania do słów x i y odpowiednio wybranych wyrazów danego ciągu, otrzymać w obu przypadkach to samo słowo.

Przykład
Słowa abba oraz ab można wyrównać za pomocą wyrazów ciągu: baaabad aa badccaa cc. Wystarczy w tym celu do słowa abba dopisać: aa oraz badccaa, zaś do słowa ab - najpierw baaabad, potem cc, a następnie aa. W obu przypadkach otrzymamy to samo słowo: abbaaabadccaa.

Zadanie

Napisz program, który:
  • wczytuje z pliku tekstowego WYR.IN długość k danego ciągu słów, a następnie opisy dwóch słów x i y oraz opisy kolejnych słów ciągu: (w1, w2, ... , wk),
  • sprawdza, czy słowa x i y można wyrównać za pomocą słów z danego ciągu i jeśli tak, znajduje minimalna liczbę operacji *, jakie trzeba w tym celu wykonać,
  • zapisuje tę liczbę w pliku tekstowym WYR.OUT.

Wejście

  • W pierwszym wierszu jest zapisana liczba całkowita dodatnia k <= 40. Jest to długość ciągu słów (w1, w2, ... , wk).
  • W drugim i trzecim wierszu znajdują się opisy słów x i y.
  • W następnych k wierszach znajdują się opisy kolejnych słów ciągu (w1, w2, ... , wk) - każdy opis w osobnym wierszu.
  • Opis słowa składa się z liczby naturalnej, będącej długością tego słowa, oraz z samego słowa w postaci ciągu znaków. Liczba jest oddzielona od słowa pojedynczym odstępem.
  • Każde słowo składa się wyłącznie z małych liter alfabetu angielskiego od a do z i ma długość nie większą niż 2000.
  • Suma długości wszystkich danych słów jest nie większa niż 5000.

Wyjście

W pliku WYR.OUT należy zapisać:
  • jedną liczbę całkowitą nieujemną, to jest minimalną liczbę operacji *, jakie trzeba wykonać, aby wyrównać dane słowa x i y,
  • albo jedno słowo NIE, jeśli słów nie można wyrównać.

Przykłady

Dla pliku WYR.IN:
4
4 abba
2 ab
7 baaabad
2 aa
7 badccaa
2 cc

w pliku WYR.OUT należy zapisać jedna liczbę:
5

Dla pliku WYR.IN:
4
1 a
2 ab
2 bb
2 ab
2 ba
2 aa

w pliku WYR.OUT należy zapisać słowo:
NIE

Twój program powinien szukać pliku WYR.IN w katalogu bieżącym i tworzyć plik WYR.OUT również w bieżącym katalogu. Plik zawierający napisany przez Ciebie program w postaci źródłowej powinien mieć nazwę WYR.???, gdzie zamiast ??? należy wpisać co najwyżej trzyliterowy skrót nazwy użytego języka programowania. Ten sam program w postaci wykonalnej powinien być zapisany w pliku WYR.EXE.




Wersja do druku