Wyrównywanie słów
Limit pamięci: 32 MB
Dane są dwa słowa i oraz skończony ciąg słów .
Operacja polega na połączeniu (konkatenacji) słowa ze słowem ,
czyli — mówiąc inaczej — na dopisaniu do słowa , z prawej jego strony, słowa .
Chcemy sprawdzić, czy słowa i 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 i
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 ze standardowego wejścia długość danego ciągu słów,
a następnie opisy dwóch słów i oraz opisy kolejnych słów ciągu ,
- sprawdza, czy słowa i można wyrównać za pomocą słów z danego ciągu i jeśli tak,
znajduje minimalną liczbę operacji , jakie trzeba w tym celu wykonać,
- zapisuje tę liczbę na standardowe wyjście.
Wejście
W pierwszym wierszu standardowego wejścia jest zapisana liczba całkowita dodatnia , .
Jest to długość ciągu słów .
W drugim i trzecim wierszu znajdują się opisy słów i .
W następnych wierszach znajdują się opisy kolejnych słów ciągu — 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ż .
Suma długości wszystkich danych słów jest nie większa niż .
Wyjście
Na standardowe wyjście należy zapisać:
- jedną liczbę całkowitą nieujemną, to jest minimalną liczbę operacji , jakie trzeba wykonać,
aby wyrównać dane słowa i ,
- albo jedno słowo NIE, jeśli słów nie można wyrównać.
Przykład
Dla danych wejściowych:
4
4 abba
2 ab
7 baaabad
2 aa
7 badccaa
2 cc
poprawną odpowiedzią jest:
5
natomiast dla danych:
4
1 a
2 ab
2 bb
2 ab
2 ba
2 aa
poprawnym wynikiem jest:
NIE
Autor zadania: Wojciech Rytter.