Polish version    English version  
  O olimpiadzie -> Zadania


 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
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.




Wersja do druku