|
|||||||||||||||
|
Równanie na słowach
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. PrzykładNiech 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ń. ZadanieNapisz program, który:
WejścieW 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. WyjścieDla 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. PrzykładDla pliku tekstowego ROW.IN: 1 5 4 2 4 4 2 5 1bad1 4 acbepoprawnym rozwiązaniem jest plik wyjściowy ROW.OUT: 16
|