Từ Fibonacci
Đề bài
Mô tả
Dãy các từ Fibonacci (các xâu bit) được định nghĩa như sau:
Ở đây là phép ghép xâu. Vài phần tử đầu tiên của dãy là:
| 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 và một số , hỏi xuất hiện bao nhiêu lần trong ?
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 ().
- Dòng thứ hai chứa mẫu bit (chỉ gồm các ký tự
0và1). Mẫu khác rỗng và có độ dài không quá 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 đó là số thứ tự test (bắt đầu từ ) và là số lần xuất hiện của mẫu trong . 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 .
Ràng buộc
- .
- , chỉ gồm các ký tự
0và1. - Đáp án nhỏ hơn .
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 |
chứa lần 10, lần 01 và lần 101 (các lần xuất hiện của 101 chồng lên nhau, ví dụ ở vị trí và ). chứa 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). chứa 0 một lần, không chứa 0. chứa 11 đúng một lần. Mẫu 1011 dài hơn nên không xuất hiện. |
Bình luận