| Historia OI -> III OI 1995/1996 -> Zadania |  |
|
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:
FIB1 = b
FIB2 = a
FIBk+2 = FIBk+1*FIBk
dla k >= 1,
gdzie * jest znakiem operacji łączenia (konkatenacji) słów.
Mamy zatem:
FIB3 = ab;
FIB4 = aba;
FIB5 = abaab;
FIB6 = 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 FIBn.
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.