Olimpiada Informatyczna

III Olimpiada Informatyczna 1995/96

Zadanie: FIB

Autor: Wojciech Rytter

Słowa Fibonacciego

Zawody II stopnia

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

Słowa Fibonacciego definiujemy podobnie jak liczby Fibonacciego:
FIB₁ = b FIB₂ = a FIB_k+2 = FIB_k+1*FIB_k dla k >= 1,
gdzie * jest znakiem operacji łączenia (konkatenacji) słów.

Mamy zatem:
FIB₃ = ab; FIB₄ = aba; FIB₅ = abaab; FIB₆ = abaababa.

Zadanie

Napisz program, który:

wczytuje z pliku tekstowego FIB.IN słowo złożone z co najmniej jednej i co najwyżej 30 liter a lub b oraz liczbę całkowitą dodatnią n <= 200,
oblicza, ile razy dane słowo występuje w n-tym słowie Fibonacciego FIBn (poszczególne wystąpienia danego słowa mogą częściowo na siebie zachodzić),
zapisuje wynik w pliku tekstowym FIB.OUT.

Wejście

W pierwszym wierszu pliku tekstowego FIB.IN jest zapisane jedno słowo złożone z co najmniej jednej i co najwyżej 30 małych liter a lub b. W drugim wierszu jest zapisana jedna liczba całkowita dodatnia n <= 200.

Wyjście

W pliku tekstowym FIB.OUT należy zapisać jedną liczbę całkowitą nieujemną, która jest liczbą wystąpień danego słowa w n-tym słowie Fibonacciego FIB_n.

Przykład

Dla pliku FIB.IN:
aba
6

w pliku FIB.OUT należy zapisać jedną liczbę:
3

Twój program powinien szukać pliku FIB.IN w katalogu bieżącym i tworzyć plik FIB.OUT również w bieżącym katalogu. Plik zawierający napisany przez Ciebie program w postaci źródłowej powinien mieć nazwę FIB.???, 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 FIB.EXE.