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.