In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
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.
The sequence of Fibonacci words is defined as follows: , , . is the concatenation of and .
The first few Fibonacci words are: b,a,ab,aba,abaab,abaababa,abaababaabaab,...
A word is a subword of a word if can be written as for some (possibly empty) words and .
Write a program which:
The first line contains one integer (). We will examine the Fibonacci word . The second line contains one word (a sequence of no more than and no less than one letter a and/or b).
In the first and only line your program should write two numbers separated by a single space. The former is the number of times the word occurs in as a subword. The latter is the number of nonempty words which occur in as subwords at least as frequently as occurs in .
Both numbers should be written modulo (you should write the remainder of the division of these numbers by ).
You can assume, that the word is a subword of the given Fibonacci word.
For the input data:
5 aba
the correct result is:
3 5
The subwords of which occur in at least as frequently as aba are: a, b, ab, ba and aba.
Task author: Jakub Radoszewski.