|
|
VIII Olimpiada Informatyczna 2000/2001
|
|
Zadanie: NAS
|
Autor: Adam Malinowski, Wojciech Rytter
|
Naszyjniki
| Zawody III stopnia, dzień pierwszy |
27 marzec 2001
|
| Plik źródłowy: | NAS.??? (np. pas, c, cpp) |
| Plik wykonywalny: | NAS.exe |
| Plik wejściowy: | NAS.in |
| Plik wyjściowy: | NAS.out |
W Bajtocji żyje bardzo znany jubiler Bajtazar.
Zajmuje się on wyrobem naszyjników.
Naszyjniki są zrobione z drogocennych kamieni nanizanych na nitkę.
Do wyrobu naszyjników używa się 26-ciu rodzajów kamieni, będziemy je oznaczać małymi literami alfabetu (angielskiego): a-z.
Bajtazar postawił sobie za punkt honoru, aby nigdy nie wykonać dwóch takich samych naszyjników i przechowuje opisy wykonanych przez siebie naszyjników.
Niektóre z tych naszyjników są bardzo długie.
Dlatego też ich opisy mają skróconą postać.
Każdy opis składa się z szeregu wielokrotnie powtórzonych sekwencji kamieni (wzorów).
Opis naszyjnika to ciąg wzorów wraz z liczbami ich powtórzeń.
Każdy wzór jest opisany za pomocą sekwencji liter reprezentujących kamienie tworzące wzór.
Przykładowo, opis:
abc 2 xyz 1 axc 3
reprezentuje naszyjnik
abcabcxyzaxcaxcaxc powstały przez dwukrotne powtórzenie wzoru
abc, jednokrotne wystąpienie wzoru xyz i trzykrotne powtórzenie wzoru axc.
Sprawę dodatkowo utrudnia fakt, iż naszyjniki nie mają widocznego początku, ani końca i można je dowolnie obracać w kółko.
Powyższy opis reprezentuje również np.
naszyjniki cabcxyzaxcaxcaxcab oraz xcaxcaxcabcabcxyza.
Zadanie
Napisz program, który:
- wczyta z pliku wejściowego nas.in dwa opisy naszyjników,
- sprawdzi, czy opisy te reprezentują takie same naszyjniki,
- zapisze wynik do pliku nas.out.
Wejście
W pierwszym i drugim wierszu pliku tekstowego nas.in znajdują się opisy naszyjników, po jednym w wierszu.
Każdy z nich składa się z sekwencji liczb całkowitych i słów złożonych z małych liter alfabetu angielskiego, pooddzielanych pojedynczymi odstępami.
Opis naszyjnika składa się z liczby całkowitej n równej liczbie wzorów występujących w opisie naszyjnika (1<=n<=1 000), po której występuje n opisów powtórzeń wzorów.
Opis powtórzeń i-tego wzoru składa się z: liczby całkowitej li równej długości wzoru (1<=li<=10 000), słowa si złożonego z li małych liter alfabetu (angielskiego) a-z, reprezentującego wzór oraz liczby całkowitej ki równej liczbie powtórzeń wzoru si (1<=ki<=100 000).
Wiadomo, że suma liczb li (dla i=1,...,n) nie przekracza 10 000.
Wyjście
Twój program powinien zapisać, w pierwszym i jedynym wierszu pliku wyjściowego nas.out, słowo "TAK", jeśli obydwa opisy przedstawiają taki sam naszyjnik, lub słowo "NIE", w przeciwnym przypadku.
Przykład
Dla pliku wejściowego nas.in:
3 3 abc 2 3 xyz 1 3 axc 3
4 4 cabc 1 4 xyza 1 3 xca 3 1 b 1
poprawną odpowiedzią jest plik wyjściowy nas.out
TAK
|
