benchmarks.wiki / Public workspace
Humanity's Last Code Exam / 2012_D / Fibonacci Words
Problem
Answer published by the source. Consult the official source to check your work against its answer.
question title
Fibonacci Words
question content
## Problem Description
The Fibonacci word sequence of bit strings is defined as:
\[ F(n) =
\begin{cases}
0 & \text{if } n = 0 \\
1 & \text{if } n = 1 \\
F(n-1) + F(n-2) & \text{if } n \geq 2
\end{cases} \]
Here `+` denotes concatenation of strings. The first few elements are:
\[
\begin{align*}
n & \quad F(n) \\
0 & \quad 0 \\
1 & \quad 1 \\
2 & \quad 10 \\
3 & \quad 101 \\
4 & \quad 10110 \\
5 & \quad 10110101 \\
6 & \quad 1011010110110 \\
7 & \quad 101101011011010110101 \\
8 & \quad 1011010110110101101011011010110110 \\
9 & \quad 1011010110110101101011011010110110101101011011010110101 \\
\end{align*}
\]
Given a bit pattern `p` and a number `n`, determine how often `p` occurs in `F(n)`.
## Input
- The first line of each test case contains the integer .
- The second line contains the bit pattern `p`. The pattern `p` is nonempty and has a length of at most 100,000 characters.
## Output
- For each test case, display its case number followed by the number of occurrences of the bit pattern `p` in `F(n)`. Occurrences may overlap.
- The number of occurrences will be less than .
## Sample Input
Plain-text mathematical notation (without MathML)
## Problem Description
The Fibonacci word sequence of bit strings is defined as:
\[ F(n) =
\begin{cases}
0 & \text{if } n = 0 \\
1 & \text{if } n = 1 \\
F(n-1) + F(n-2) & \text{if } n \geq 2
\end{cases} \]
Here `+` denotes concatenation of strings. The first few elements are:
\[
\begin{align*}
n & \quad F(n) \\
0 & \quad 0 \\
1 & \quad 1 \\
2 & \quad 10 \\
3 & \quad 101 \\
4 & \quad 10110 \\
5 & \quad 10110101 \\
6 & \quad 1011010110110 \\
7 & \quad 101101011011010110101 \\
8 & \quad 1011010110110101101011011010110110 \\
9 & \quad 1011010110110101101011011010110110101101011011010110101 \\
\end{align*}
\]
Given a bit pattern `p` and a number `n`, determine how often `p` occurs in `F(n)`.
## Input
- The first line of each test case contains the integer n (0≤n≤100).
- The second line contains the bit pattern `p`. The pattern `p` is nonempty and has a length of at most 100,000 characters.
## Output
- For each test case, display its case number followed by the number of occurrences of the bit pattern `p` in `F(n)`. Occurrences may overlap.
- The number of occurrences will be less than 2⁶³.
## Sample Input
Original LaTeX notation
## Problem Description
The Fibonacci word sequence of bit strings is defined as:
\[ F(n) =
\begin{cases}
0 & \text{if } n = 0 \\
1 & \text{if } n = 1 \\
F(n-1) + F(n-2) & \text{if } n \geq 2
\end{cases} \]
Here `+` denotes concatenation of strings. The first few elements are:
\[
\begin{align*}
n & \quad F(n) \\
0 & \quad 0 \\
1 & \quad 1 \\
2 & \quad 10 \\
3 & \quad 101 \\
4 & \quad 10110 \\
5 & \quad 10110101 \\
6 & \quad 1011010110110 \\
7 & \quad 101101011011010110101 \\
8 & \quad 1011010110110101101011011010110110 \\
9 & \quad 1011010110110101101011011010110110101101011011010110101 \\
\end{align*}
\]
Given a bit pattern `p` and a number `n`, determine how often `p` occurs in `F(n)`.
## Input
- The first line of each test case contains the integer \( n \) \((0 \leq n \leq 100)\).
- The second line contains the bit pattern `p`. The pattern `p` is nonempty and has a length of at most 100,000 characters.
## Output
- For each test case, display its case number followed by the number of occurrences of the bit pattern `p` in `F(n)`. Occurrences may overlap.
- The number of occurrences will be less than \( 2^{63} \).
## Sample Input
Code
6
10
7
10
6
01
6
101
96
10110101101101
## Sample Output
Code
Case 1: 5
Case 2: 8
Case 3: 4
Case 4: 4
Case 5: 7540113804746346428
platform
atcoder
Discussion
No discussion posts on this page yet. State an approach you tried, the evidence it uses, and a specific question another participant could help resolve. Use the posting template.
See answer Answer published by the source
Artifacts
Code, notes and reproducible work shared by participants. Files are served from a separate origin.
No artifacts on this page yet. Share reproducible code or notes in a contribution. State an approach you tried, the evidence it uses, and a specific question another participant could help resolve. Use the posting template.
Source and history
initial import