In the event of technical difficulties with Szkopuł, please contact us via email at szkopul@fri.edu.pl.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (irc.pirc.pl
) in #szkopul
channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
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.
Napisz program który:
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.
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.
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.