trang chủ / đề bài / icpcwf12_d

Từ Fibonacci

Đề bài

Mô tả

Dãy các từ Fibonacci (các xâu bit) được định nghĩa như sau:

F(n)={0nếu n=01nếu n=1F(n−1)+F(n−2)nếu n≥2

Ở đây + là phép ghép xâu. Vài phần tử đầu tiên của dãy là:

n F(n)
0 0
1 1
2 10
3 101
4 10110
5 10110101
6 1011010110110
7 101101011011010110101
8 1011010110110101101011011010110110
9 1011010110110101101011011010110110101101011011010110101

Cho một mẫu bit p và một số n, hỏi p xuất hiện bao nhiêu lần trong F(n)?

Dữ liệu vào

Dữ liệu gồm nhiều test, đọc tới hết dữ liệu. Mỗi test gồm hai dòng:

  • Dòng thứ nhất chứa số nguyên n (0≤n≤100).
  • Dòng thứ hai chứa mẫu bit p (chỉ gồm các ký tự 0 và 1). Mẫu p khác rỗng và có độ dài không quá 100000 ký tự.

Dữ liệu ra

Với mỗi test, in ra số thứ tự của test theo dạng Case i: x, trong đó i là số thứ tự test (bắt đầu từ 1) và x là số lần xuất hiện của mẫu p trong F(n). Các lần xuất hiện có thể chồng lên nhau. Số lần xuất hiện luôn nhỏ hơn 263.

Ràng buộc

  • 0≤n≤100.
  • 1≤|p|≤100000, p chỉ gồm các ký tự 0 và 1.
  • Đáp án nhỏ hơn 263.

Ví dụ

Input Output Giải thích
6
10
7
10
6
01
6
101
96
10110101101101
Case 1: 5
Case 2: 8
Case 3: 4
Case 4: 4
Case 5: 7540113804746346428
F(6)=1011010110110 chứa 5 lần 10, 4 lần 01 và 4 lần 101 (các lần xuất hiện của 101 chồng lên nhau, ví dụ ở vị trí 1 và 3). F(7)=101101011011010110101 chứa 8 lần 10.
0
0
1
0
5
11
3
1011
Case 1: 1
Case 2: 0
Case 3: 1
Case 4: 0
Ví dụ thêm (không có trong đề gốc). F(0)=0 chứa 0 một lần, F(1)=1 không chứa 0. F(5)=10110101 chứa 11 đúng một lần. Mẫu 1011 dài hơn F(3)=101 nên không xuất hiện.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0