V Olimpiada Informatyczna 1997/98
|
Zadanie: ROW
|
Autor: Wojciech Rytter
|
II ETAP, PIERWSZY DZIEŃ ZAWODÓW - PIĽTEK 13 LUTEGO 1998 r. |
Plik źródłowy: | ROW.??? (np. pas, c, cpp) |
Plik wykonywalny: | ROW.exe |
Plik wejściowy: | ROW.in |
Plik wyjściowy: | ROW.out |
Słowem dwójkowym nazywamy każdy niepusty ciąg złożony z 0 lub 1. Równanie na słowach ma postać x1x2...xl = y1y2...yr, gdzie xi i yj są cyframi dwójkowymi (0 lub 1) lub zmiennymi, to jest małymi literami alfabetu angielskiego. Dla każdej zmiennej jest ustalona długość słów dwójkowych, które można podstawiać w jej miejsce. Długość tę nazywamy długością zmiennej. Rozwiązanie równania na słowach polega na przypisaniu każdej zmiennej słowa dwójkowego o odpowiadającej tej zmiennej długości, w taki sposób, by po zastąpieniu zmiennych w równaniu przez przypisane im słowa, obie strony równania (słowa dwójkowe) były takie same.
Dla danego równania na słowach policz ile jest różnych rozwiązań tego równania.
Niech 4, 2, 4, 4, 2 będą długościami zmiennych a, b, c, d, e w poniższym równaniu:
1bad1 = acbeTo równanie ma 16 różnych rozwiązań.
Napisz program, który:
W pierwszym wierszu pliku wejściowego ROW.IN znajduje się liczba całkowita x, 1 <= x <= 5. Jest to liczba równań. Następne wiersze zawierają opisy x równań. Na każdy opis składa się 6 wierszy. Między kolejnymi opisami nie ma pustych wierszy. Każde równanie jest opisane w następujący sposób: W pierwszym wierszu opisu znajduje się liczba całkowita k, 0 <= k <= 26. Jest to liczba różnych zmiennych w równaniu. Przyjmujemy, że zawsze zmiennymi jest k pierwszych małych liter alfabetu angielskiego. W drugim wierszu jest zapisany ciąg k liczb całkowitych dodatnich oddzielonych pojedynczymi odstępami. Te liczby to długości k kolejnych zmiennych a, b, ... występujących w równaniu. Trzeci wiersz opisu zawiera tylko jedną dodatnią liczbę całkowitą l. Jest to długość lewej strony równania - tj. długość słowa utworzonego z cyfr 0 lub 1 i jednoliterowych zmiennych. W następnym wierszu jest zapisana lewa strona równania jako ciąg l cyfr lub zmiennych bez odstępów między nimi. Następne dwa wiersze zawierają opis prawej strony równania. Pierwszy z tych wierszy zawiera dodatnią liczbę r. Jest to długość prawej strony równania. Drugi z wierszy zawiera prawą stronę równania zapisaną w taki sam sposób jak jego lewa strona. Liczba cyfr plus suma długości wszystkich zmiennych (licząc wszystkie wystąpienia każdej zmiennej) po każdej stronie równania nie przekracza 10000.
Dla każdego i, 1 <= i <= x, Twój program powinien zapisać w i-tym wierszu pliku wyjściowego ROW.OUT liczbę różnych rozwiązań i-tego równania.
Dla pliku tekstowego ROW.IN:
1 5 4 2 4 4 2 5 1bad1 4 acbepoprawnym rozwiązaniem jest plik wyjściowy ROW.OUT:
16