IV Olimpiada Informatyczna 1996/97

Zadanie: LIC
Autor: Wojciech Rytter
Liczba Wyborów Symetrycznych

Zawody I stopnia  
Plik źródłowy: LIC.??? (np. pas, c, cpp)
Plik wykonywalny: LIC.exe
Plik wejściowy: LIC.in
Plik wyjściowy: LIC.out

Dane są dwa ciągi słów (xi) oraz (yi), gdzie: 1<= i <= n oraz 1 <= n <= 30. Kolejno dla każdego i od 1 do n wybieramy jedno z dwóch słów: xi albo yi i wybrane słowa składamy (kolejne wybrane słowo dopisujemy do poprzednich z prawej strony). Wybór składa się z n decyzji, czy w kolejnym kroku wybrać odpowiedni i-ty wyraz z pierwszego, czy z drugiego ciągu słów. Bardziej formalnie: wybór jest n wyrazowym ciągiem liczb 1 lub 2. Różne wybory mogą dać w wyniku to samo słowo. Wybór nazywamy symetrycznym, gdy jego wynikiem jest palindrom - tzn. takie słowo, które nie zmienia się, gdy je czytamy od strony prawej do lewej.

Zadanie

Napisz program, który:

Wejście

W pierwszym wierszu pliku tekstowego LIC.IN jest zapisana jedna liczba całkowita dodatnia n Ł 30. W następnych n wierszach są zapisane kolejne słowa ciągu (xi) - każde w osobnym wierszu. W następnych n wierszach są zapisane - w taki sam sposób - kolejne słowa ciągu (yi). Wszystkie słowa składają się wyłącznie z małych liter alfabetu angielskiego od a do z i mają długość nie mniejszą niż 1 i nie większą niż 400.

Wyjście

W pliku tekstowym LIC.OUT należy zapisać jedną liczbę całkowitą nieujemną, a mianowicie liczbę wszystkich wyborów symetrycznych.

Przykład

Dla pliku LIC.IN:

5
ab
a
a
ab
a
a
baaaa
a
a
ba
poprawnym rozwiązaniem jest plik LIC.OUT:
12

Twój program powinien szukać pliku LIC.IN w katalogu bieżącym i tworzyć plik LIC.OUT również w bieżącym katalogu. Plik zawierający napisany przez Ciebie program w postaci źródłowej powinien mieć nazwę LIC.???, gdzie zamiast ??? należy wpisać co najwyżej trzyliterowy skrót nazwy użytego języka programowania. Ten sam program w postaci wykonalnej powinien być zapisany w pliku LIC.EXE