Równanie na słowach
Limit pamięci: 32 MB
Słowem dwójkowym nazywamy każdy niepusty ciąg złożony z lub
.
Równanie na słowach ma postać
, gdzie
i
są cyframi dwójkowymi (
lub
) 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.
Przykład
Niech będą długościami zmiennych
w poniższym równaniu:
To równanie ma
różnych rozwiązań.
Zadanie
Napisz program, który:
- wczytuje ze standardowego wejścia liczbę równań i ich opisy;
- znajduję liczbę rozwiązań każdego równania;
- zapisuje wyniki na standardowe wyjście.
Wejście
W pierwszym wierszu standardowego wejścia znajduje się liczba całkowita ,
.
Jest to liczba równań.
Następne wiersze zawierają opisy
równań.
Na każdy opis składa się
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 ,
.
Jest to liczba różnych zmiennych w równaniu.
Przyjmujemy, że zawsze zmiennymi jest
pierwszych małych liter alfabetu angielskiego.
W drugim wierszu jest zapisany ciąg
liczb całkowitych dodatnich oddzielonych pojedynczymi odstępami.
Te liczby to długości
kolejnych zmiennych
występujących w równaniu.
Trzeci wiersz opisu zawiera tylko jedną dodatnią liczbę całkowitą .
Jest to długość lewej strony równania — tj. długość słowa utworzonego z cyfr
lub
i jednoliterowych zmiennych.
W następnym wierszu jest zapisana lewa strona równania jako ciąg
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ę
.
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
.
Wyjście
Dla każdego ,
, Twój program powinien zapisać w
-tym wierszu standardowego wyjścia liczbę różnych rozwiązań
-tego równania.
Przykład
Dla danych wejściowych:
1 5 4 2 4 4 2 5 1bad1 4 acbe
poprawną odpowiedzią jest:
16
Autor zadania: Wojciech Rytter.