GFSSOC '15 Fall Practice P4 - Bruno and Fibonacci

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem types

Bruno's chemistry homework requires him to repeatedly analyse DNA sequences. After the thousandth or so sequence, Bruno's brain is numb, and he starts to imagine patterns. A DNA sequence in his textbook is represented as a collection of A, T, C, and G characters. He thinks that a particular sequence in the book places the As in a very strange way. Bruno's speculation is that for every integer k which belongs to the Fibonacci sequence, the k^\text{th} letter of this DNA sequence is an A. Furthermore, Bruno believes that As do not appear at any index (the first letter is index one) which does not belong to the Fibonacci sequence. Half asleep already, Bruno calls you to confirm his suspicions, and what better way to do it than through a program?

Input Specification

The first line contains one integer N (1 \le N \le 500), the length of the DNA sequence.

The second line contains one string S, the DNA sequence.

Output Specification

If Bruno's suspicions are correct, output the string That's quite the observation!. Otherwise, output the string Bruno, GO TO SLEEP.

Sample Input


Sample Output

That's quite the observation!

Explanation for Sample Output

Notice that the 1st, 2nd, 3rd, 5th, 8th, and 13th characters are A, and there are no more As outside of these. If you may recall, the numbers of the Fibonacci sequence below 20 are 1, 1, 2, 3, 5, 8, 13. Since all these numbers match to As in the sequence, Bruno's observation is valid!


  • 6
    RedcXca  commented on May 17, 2021, 1:28 a.m.

    Bruno, GO TO SLEEP.