Słowa Fibonacciego
Limit pamięci: 64 MB
Ciąg słów Fibonacciego definiujemy następująco:
,
,
.
W powyższym zapisie określamy jako sklejenie słów
i .
Kilka kolejnych słów Fibonacciego to:
b,a,ab,aba,abaab,abaababa,abaababaabaab,...
Słowo jest podsłowem slowa , jeżeli słowo możemy zapisać
jako , gdzie i są pewnymi (być może pustymi) słowami.
Zadanie
Napisz program który:
-
wczyta ze standardowego wejścia jedno słowo złożone z liter a i b
i numer słowa Fibonacciego,
-
wyznaczy liczbę wystąpień wczytanego słowa jako podsłowa w danym słowie
Fibonacciego, a także liczbę słów, których liczba wystąpień jako
podsłów w tym słowie Fibonacciego jest nie mniejsza od tej liczby,
-
wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu znajduje się jedna liczba całkowita
(), oznaczająca numer słowa
Fibonacciego.
W drugim wierszu wejścia znajduje się jedno
słowo, które składa się z nie więcej niż , oraz nie mniej
niż jednej litery a lub b.
Wyjście
W pierwszym i jedynym wierszu należy wypisać dwie liczby
całkowite oznaczające resztę z dzielenia przez liczby wystąpień
wczytanego słowa jako podsłowa danego słowa Fibonacciego oraz
resztę z dzielenia przez liczby niepustych słów (złożonych
z liter a i b), których liczba wystąpień jako podsłów danego
słowa Fibonacciego jest nie mniejsza od liczby wystąpień wczytanego
słowa (dane słowo wlicza się oczywiście do tych podsłów).
Możesz założyć, że podane na wejściu słowo jest podsłowem danego
na wejściu słowa Fibonacciego.
Przykład
Dla danych wejściowych:
5
aba
poprawną odpowiedzią jest:
3 5
Podsłowami słowa spełniającymi warunki zadania są:
a, b, ab, ba i wreszcie aba.
Autor zadania: Jakub Radoszewski.