F005A. Paraules de Fibonacci P50726


Statement
 

pdf   zip

html

The words of Fibonacci F1, F2, F3, … are described in the following way:

  • F1 = “a”.
  • F2 = “b”.
  • For every n ≥ 3, Fn is the result of concatenate Fn−2 with Fn−1.

The first seven words of the sequence of Fibonacci are: F1 = “a”, F2 = “b”, F3 = “ab”, F4 = “bab”, F5 = “abbab”, F6 = “bababbab” and F7 = “abbabbababbab”.

Your task is to write a program that, given a sequence of words, prints if they are Fibonacci words or they are not. For those that are it, you must indicate their position in the sequence.

Input

The input is a sequence of words only composed by the letters a and b. None of the words will have more than 1000 letters.

Output

For each Word, your program must indicate its position in the sequence, or print that it is not a word of Fibonacci, following the format of the instance.

Hint

Notice that the length of a word of Fibonacci increases very fast. Therefore, there are few words of Fibonacci having size 1000 or less (in fact, there are exactly 16). Calculate all of them at the beginning of the program.

Observations

  • Remember that a string s with n characters c can be declared like this: string s(n, c);
  • Remember also that the string operations like s += ’a’;, s1 += s2; or s = s1 + s2; are not allowed.
Public test cases
  • Input

    a
    b
    ba
    aaa
    bb
    bababbab
    

    Output

    a is the word number 1
    b is the word number 2
    ba is not a Fibonacci word
    aaa is not a Fibonacci word
    bb is not a Fibonacci word
    bababbab is the word number 6
    
  • Information
    Author
    Professorat de P1
    Language
    English
    Translator
    Carlos Molina
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++ Python