|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||1024 MB||3||2||2||66.667%|
Aron likes Fibonacci numbers. He likes them so much he actually got bored of the numbers themselves and decided to invent other combinatorial objects based on them instead.
His first invention is the Fibonacci string. We call a string consisting of only letters $a$ and $b$, with exactly $n$ letters $a$ without any two consecutive letters $a$ a Fibonacci string of the $n$:th order.
Given a string $X$ of $a$:s and $b$:s, compute the sum of orders of all Fibonacci strings that are substrings of $X$. Note that if a string $X$ appears multiple times, its order should be counted once for every occurance.
Assume that Aron has the string $abaaba$. This contains the Fibonacci string $a$ four times, $ab$ two times, $ba$ two times and $aba$ two times. The sum of their orders is $4 \cdot 1 + 2 \cdot 1 + 2 \cdot 1 + 2 \cdot 2 = 4 + 2 + 2 + 4 = 12$.
Write a program that given $X$ computes the sum of orders of all Fibonacci substrings of $X$. You should implement the function
fibonacci(N, X)- this function will be called exactly once by the judge.
N: an integer - the number of charaters in the string $X$.
X: a string consisting of $X$ characters, consisting only lowercase letters $a$ and $b$.
A code skeleton containing the function to be implemented, together with a sample grader, can be found at attachments.zip.
The sample judge reads input in the following format:
The judge writes a single line containing the return value of
C++17, Java 8, C++14, Java 8 (OpenJDK), Java 11, C++20, Java 15, C++14 (Clang), C++17 (Clang), C++20 (Clang)