Polish version    English version  
  O olimpiadzie -> Zadania -> V OI 1997/1998


 Aktualności
 O olimpiadzie
O olimpiadzie
Zadania
I OI 1993/1994
II OI 1994/1995
III OI 1995/1996
IV OI 1996/1997
V OI 1997/1998
VI OI 1998/1999
VII OI 1999/2000
VIII OI 2000/2001
IX OI 2001/2002
X OI 2002/2003
XI OI 2003/2004
XII OI 2004/2005
XIII OI 2005/2006
XIV OI 2006/2007
XV OI 2007/2008
Archiwum zadań
Ankieta OI
 Komitety
 XVIII OI 2010/2011
 Historia OI
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
V Olimpiada Informatyczna 1997/98

Zadanie: ROW
Autor: Wojciech Rytter
Równanie na słowach

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.

Przykład

Niech 4, 2, 4, 4, 2 będą długościami zmiennych a, b, c, d, e w poniższym równaniu:

1bad1 = acbe
To równanie ma 16 różnych rozwiązań.

Zadanie

Napisz program, który:

  • wczytuje z pliku tekstowego ROW.IN liczbę równań i ich opisy;
  • znajduję liczbę rozwiązań każdego równania;
  • zapisuje wyniki w pliku tekstowym ROW.OUT.

Wejście

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.

Wyjście

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.

Przykład

Dla pliku tekstowego ROW.IN:

1
5
4 2 4 4 2
5
1bad1
4
acbe
poprawnym rozwiązaniem jest plik wyjściowy ROW.OUT:
16





Wersja do druku