Problem description

Back

Show PDF

.desc_header { margin-bottom: 2em; text-align: center; } .desc_title { font-size: 200%; text-decoration: underline; padding: 0em 0.2em; display: inline-block; } .desc_code { padding: 0em 0.2em; font-weight: bold; display: inline-block; } .desc_meta { margin: 0.5em; } .desc_memlimit { padding: 0em 1.25em; display: inline-block; } .desc_timelimit { padding: 0em 1.25em; display: inline-block; } .desc .example-test { width: 100%; margin-top: 10px; } .desc .example-test td { vertical-align: top; } .desc .example-test pre { margin-top: 5px; } Wzorzec (D) Limit pamięci: 1000 MB Limit czasu: 1.00 s Bajtazar pracuje nad nowym systemem wyszukiwanai plików i eksperymentuje z dopasowywaniem wzorców. Aktualnie posiada zestaw N wzorców P1, P2, …, PN. Każdy wzorzec opisuje napisy, które do niego pasują. Teraz chce sprawdzić, czy da się znaleźć jeden napis pasujący do wszystkich wzorców. Wzorzec składa się z co najmniej jednego znaku specjalnego * i może (ale nie musi) zawierać wielkie litery alfabetu angielskiego. Mówimy, że napis S pasuje do wzorca P, jeśli można zastąpić każdą gwiazdkę * w P pewnym ciągiem (być może pustym) wielkich liter tak, aby po tych podstawieniach otrzymać dokładnie napis S. Wzorzec A*B pasuje do: AB, AXB, ABJB, AHELLOB. Wzorzec *ABC* pasuje do: ABC, ZABCQ, HELLOABC. Wzorzec AB*CD nie pasuje do: ABDC, ABCDX. Bajtazar zastanawia się, czy istnieje taki napis S (składający się wyłącznie z wielkich liter alfabetu angielskiego), który pasuje do wszystkich N wzorców jednocześnie oraz nie przekracza długości 10 000 znaków. Jeśli taki napis istnieje, należy wypisać dowolny z nich. Jeżeli nie istnieje żaden napis spełniający powyższych wymagań, należy wypisać *. Wejście W pierwszym wierszu wejścia znajduje się jedna liczba całkowita T - liczba zestawów danych. Następnie podawane są opisy T zestawów danych. Pierwszy wiersz każdego zestawu zawiera jedną liczbę całkowitą N – liczbę wzorców. W kolejnych N wierszach znajdują się wzorce P1, P2, …, PN. Każdy wzorzec jest ciągiem znaków składającym się z wielkich liter alfabetu angielskiego oraz gwiazdek (*). Wyjście Dla każdego zestawu danych wypisz w osobnym wierszu odpowiedni napis o długości co najwyżej 10 000 znaków. Jeżeli nie istnieje żaden napis spełniający powyższych wymagań, należy wypisać *. Ograniczenia 1 ≤ T ≤ 100 2 ≤ N ≤ 50 2 ≤ |Pi| ≤ 100 Każdy wzorzec zawiera co najmniej jedną gwiazdkę. Podzadania Podzadanie Warunki Punkty 1 Każdy wzorzec zawiera dokładnie jedną * i jest ona pierwszym znakiem każdego wzorca 10 2 Każdy wzorzec zawiera dokładnie jedną * 30 3 Brak dodatkowych ograniczeń 60 Przykład Wejście Wyjście Wyjaśnienie 2 5 *CONUTS *COCONUTS *OCONUTS *CONUTS *S 2 *XZ *XYZ COCONUTS * W pierwszym przypadku najdłuższy sufiks “COCONUTS” zawiera wszystkie pozostałe krótsze końcówki, więc jest poprawnym rozwiązaniem. W drugim przypadku wymagane końcówki “XZ” oraz “XY” wykluczają się wzajemnie (słowo nie może kończyć się na dwie różne litery), co oznacza brak rozwiązania.

Podzadanie	Warunki	Punkty
1	Każdy wzorzec zawiera dokładnie jedną `*` i jest ona pierwszym znakiem każdego wzorca	10
2	Każdy wzorzec zawiera dokładnie jedną `*`	30
3	Brak dodatkowych ograniczeń	60

Wejście	Wyjście	Wyjaśnienie
`2 5 CONUTS COCONUTS OCONUTS CONUTS S 2 XZ *XYZ`	`COCONUTS *`	W pierwszym przypadku najdłuższy sufiks “COCONUTS” zawiera wszystkie pozostałe krótsze końcówki, więc jest poprawnym rozwiązaniem. W drugim przypadku wymagane końcówki “XZ” oraz “XY” wykluczają się wzajemnie (słowo nie może kończyć się na dwie różne litery), co oznacza brak rozwiązania.