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.