Xâu Fibonacci (FIB2)

Nguồn: Đề luyện thi HSG Tin học Độ khó: Khá Xâu Fibonacci Chia để trị

Đề bài

XÂU FIBONACCI

Xâu Fibonacci thường được sử dụng để rèn luyện kỹ năng xử lý khi giới thiệu các giải thuật xử lý xâu.

Xét dãy xâu $F_0, F_1, F_2, \dots$ được xây dựng theo quy tắc sau:

• $F_0 = \text{'a'}$,
• $F_1 = \text{'b'}$,
• $F_n = F_{n-2} + F_{n-1}$, $n \gt 1$.

Yêu cầu: Cho hai số nguyên $n, k$ $(1 \le n \le 45)$, $k$ không vượt quá độ dài xâu $F_n$. Hãy xác định số lượng ký tự $\text{'a'}$ xuất hiện trong $k$ ký tự đầu tiên của xâu $F_n$.

Dữ liệu: vào từ tập tin văn bản FIB2.INP

• Dòng đầu tiên chứa số nguyên $T$ – số lượng tests cần xử lý $(1 \le T \le 100)$,
• Mỗi dòng trong $T$ dòng sau chứa 2 số nguyên $n, k$.

Kết quả: ghi ra tập tin văn bản FIB2.OUT, kết quả mỗi test đưa ra trên một dòng dưới dạng số nguyên.

Lưu ý: trên hệ thống chấm online, chương trình đọc dữ liệu từ bàn phím (stdin) và ghi ra màn hình (stdout), không dùng file.

Ví dụ – FIB2.INP

4
0 1
1 1
3 2
7 7

Ví dụ – FIB2.OUT

1
0
1
3

Lời mở đầu

Bài này nhìn đề thì tưởng dễ: cứ dựng xâu ra rồi đếm thôi. Nhưng chính cái "dễ" đó lại là cái bẫy 😁. Mình sẽ đi từ cách làm theo đúng đề để các bạn thấy nó "toang" ở đâu, rồi mới tới tư tưởng chia để trị (divide and conquer) để giải trọn vẹn.

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Mình giải thích ví dụ mẫu cho bạn nào chưa hiểu đề. Liệt kê vài xâu đầu tiên (dấu | để các bạn thấy mỗi xâu được ghép từ 2 xâu trước như thế nào):

$F_i$	Xâu	Độ dài	Số 'a'
F0	a	1	1
F1	b	1	0
F2	a|b	2	1
F3	b|ab	3	1
F4	ab|bab	5	2
F5	bab|abbab	8	3
F6	abbab|bababbab	13	5
F7	bababbab|abbabbababbab	21	8

• 0 1: 1 ký tự đầu của $F_0$ = a ⇒ có 1 chữ 'a'.
• 1 1: 1 ký tự đầu của $F_1$ = b ⇒ 0.
• 3 2: 2 ký tự đầu của $F_3$ = ba ⇒ 1.
• 7 7: 7 ký tự đầu của $F_7$ = bababba ⇒ 3.

Để ý nhỏ

Đề ghi $1 \le n \le 45$ nhưng ví dụ lại có test 0 1 ($n = 0$). Vậy code của mình phải xử lý được cả $n = 0$ cho chắc ăn nha.

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Dựng xâu rồi đếm · TLE + MLECách 2Chia để trị theo độ dài · O(T·45)

Cách 1Làm đúng theo đề: dựng xâu rồi đếm

Cách đơn giản nhất là làm y như đề nói: có $F_0$, $F_1$ ban đầu rồi tạo dần $F_i = F_{i-2} + F_{i-1}$ tới $F_n$, sau đó duyệt $k$ ký tự đầu tiên của $F_n$ đếm xem có bao nhiêu chữ 'a'. Làm vậy cho từng test trong $T$ test.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;

int main(){
    // freopen("FIB2.INP", "r", stdin);   // khi thi bằng file thì bỏ // ở 2 dòng này
    // freopen("FIB2.OUT", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n, k;
        cin >> n >> k;
        string f[n + 2];
        f[0] = "a";
        f[1] = "b";
        for(int i = 2; i <= n; ++i){
            f[i] = f[i - 2] + f[i - 1];
        }
        int cnt = 0;
        for(int i = 0; i < k; ++i){
            if(f[n][i] == 'a'){
                cnt++;
            }
        }
        cout << cnt << endl;
    }
    return 0;
}

import sys

# sys.stdin = open("FIB2.INP", "r")   # khi thi bằng file thì bỏ # ở 2 dòng này
# sys.stdout = open("FIB2.OUT", "w")
input_data = sys.stdin.read().split()
it = iter(input_data)
t = int(next(it))
while t:
    t -= 1
    n = int(next(it))
    k = int(next(it))
    f = [''] * (n + 2)
    f[0] = 'a'
    f[1] = 'b'
    for i in range(2, n + 1):
        f[i] = f[i - 2] + f[i - 1]
    cnt = 0
    for i in range(k):
        if f[n][i] == 'a':
            cnt += 1
    print(cnt)

Về 2 dòng freopen

Đề gốc đọc/ghi file FIB2.INP / FIB2.OUT. Trên hệ thống chấm online thì đọc/ghi chuẩn nên mình để 2 dòng freopen (Python là 2 dòng open) ở dạng chú thích. Khi đi thi bằng file thì các bạn bỏ dấu chú thích ra là được.

C++▶ Chạy tay từng dòng codeCách 1: dựng hẳn các xâu F[0..n] rồi đếm 'a' trong k ký tự đầu của F[n].

Dữ liệu vào (stdin) – sửa thoải mái4 0 1 1 1 3 2 7 7

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4int main(){

5 // freopen("FIB2.INP", "r", stdin); // khi thi bằng file thì bỏ // ở 2 dòng này

6 // freopen("FIB2.OUT", "w", stdout);

7 ios::sync_with_stdio(0);

8 cin.tie(0);

9 cout.tie(0);

10 int t;

11 cin >> t;

12 while(t--){

13 int n, k;

14 cin >> n >> k;

15 string f[n + 2];

16 f[0] = "a";

17 f[1] = "b";

18 for(int i = 2; i <= n; ++i){

19 f[i] = f[i - 2] + f[i - 1];

20 }

21 int cnt = 0;

22 for(int i = 0; i < k; ++i){

23 if(f[n][i] == 'a'){

24 cnt++;

25 }

26 }

27 cout << cnt << endl;

28 }

29 return 0;

30}

ChậmVừaNhanhRất nhanh

Nhưng code này nộp lên hệ thống sẽ bị lỗi TLE (Time Limit Exceeded – chạy quá thời gian) và MLE (Memory Limit Exceeded – dùng quá bộ nhớ). Tại sao vậy? Các bạn nhìn cột độ dài ở bảng trên: $1, 1, 2, 3, 5, 8, 13, 21, \dots$ – chính là dãy Fibonacci! Nên $F_{45}$ chắc chắn dài khủng khiếp.

MLE: tốn gần 7 lần bộ nhớ cho phép

Tính thử dãy độ dài với $f_0 = f_1 = 1$, $f_i = f_{i-2} + f_{i-1}$ thì $f_{45} = 1\,836\,311\,903$ (1 tỷ 836 triệu). Tức là riêng $F_{45}$ đã cần lưu ~1,8 tỷ ký tự, mỗi ký tự 1 byte ⇒ $1\,836\,311\,903 / 1024 / 1024 \approx 1751$ MB. Trong khi bài chỉ cho 256 MB ⇒ vượt gần $1751 / 256 \approx 7$ lần. Đó là còn chưa tính các xâu $F_{44}, F_{43}, \dots$ cũng nằm trong mảng!

TLE

$k$ có thể bằng đúng độ dài $F_n$. Khi $n = 45$ thì riêng vòng đếm đã lặp hơn 1,8 tỷ lần; với ~$10^8$ phép tính/giây thì mất gần 20 giây, chưa kể bước nối xâu tạo $F_2, F_3, \dots, F_{45}$ trước đó, và còn nhân với $T$ test nữa.

Đánh giá độ phức tạp: cả bộ nhớ lẫn thời gian đều tỉ lệ với độ dài xâu, tức là $O(|F_n|) \approx O(1.618^n)$ cho mỗi test.

Không gian$O(|F_n|)$

Thời gian$O(T \cdot |F_n|)$

Cách 2Chia để trị theo độ dài Fibonacci – O(T·45)

Bản chất để giải bài này là tư tưởng "chia để trị". Ta không cần dựng xâu, chỉ cần 2 mảng nhỏ: độ dài và số chữ 'a' của từng $F_i$.

Thử với ví dụ của đề: $n = 7$, $k = 7$. $F_7 = F_5 + F_6$, với $F_5$ dài 8, $F_6$ dài 13. Vì $k = 7 \lt 8$ nên 7 ký tự đầu của $F_7$ nằm gọn trong $F_5$ – chỉ cần xét $F_5$ thôi.

• $F_5 = F_3 + F_4$ ($F_3$ dài 3, $F_4$ dài 5): lấy trọn $F_3$, còn cần 4 ký tự đầu của $F_4$.
• $F_4 = F_2 + F_3$ ($F_2$ dài 2, $F_3$ dài 3): lấy trọn $F_2$, còn cần 2 ký tự đầu của $F_3$.
• $F_3 = F_1 + F_2$ ($F_1$ dài 1, $F_2$ dài 2): lấy trọn $F_1$, còn cần 1 ký tự đầu của $F_2$.
• $F_2 = F_0 + F_1$: lấy trọn $F_0$. Xong!

Tổng kết lại: 7 ký tự đầu của $F_7$ gồm trọn $F_3, F_2, F_1, F_0$ ⇒ số chữ 'a' là $1 + 1 + 0 + 1 = 3$ ✔.

Như vậy nếu ngay từ đầu ta tính sẵn số chữ 'a' của từng $F_i$ thì chỉ việc cộng lại. Việc này rất dễ, vì $F_i = F_{i-2} + F_{i-1}$ nên số 'a' cũng cộng y như vậy:

Hai mảng cần tính sẵn (trong code là a[] và b[])

• Độ dài: a[0] = a[1] = 1, a[i] = a[i-2] + a[i-1] ⇒ $1, 1, 2, 3, 5, 8, 13, 21, \dots$
• Số chữ 'a': b[0] = 1 ($F_0$ = a), b[1] = 0 ($F_1$ = b), b[i] = b[i-2] + b[i-1] ⇒ $1, 0, 1, 1, 2, 3, 5, 8, \dots$

Gom khối: luôn lấy khối dài nhất có thể

Giờ thử test $n = 7$, $k = 14$. Nếu tách theo cách vừa nói thì 14 ký tự đầu gồm trọn $F_5, F_4, F_1$. Nhưng nhìn kỹ: trọn $F_5$ và trọn $F_4$ thì số chữ 'a' cũng chính bằng số chữ 'a' của $F_6$ (vì $F_6 = F_4 + F_5$) 😉. Nên ta chỉ cần quan tâm độ dài: với $k = 14$ thì khối dài nhất lấy được là $13$ (tức $F_6$), còn lại $1$.

Tương tự $k = 10$: khối dài nhất $\le 10$ là $8$ ($F_5$), còn $2$ – chính là $F_2$. Vậy $k = 10$ gồm trọn $F_5, F_2$. Dễ thấy quy luật chưa ^^

Thuật toán

Lặp khi $k \ge 2$: tìm chỉ số idx lớn nhất có a[idx] <= k (dùng upper_bound rồi lùi 1), cộng b[idx] vào đáp án, rồi k -= a[idx].

Chỗ phức tạp một chút là khi còn dư đúng 1 ký tự: độ dài 1 thì có tới 2 khả năng $F_0$ (='a') hay $F_1$ (='b'). Phần này các bạn thử tự nhìn ra quy luật trước nhé, còn đây là gợi ý của mình: để ý ký tự đầu của $F_m$: là 'a' khi $m$ chẵn và 'b' khi $m$ lẻ (vì $F_m$ bắt đầu bằng $F_{m-2}$, cứ lùi dần về $F_0$ = a hoặc $F_1$ = b), và ký tự dư đó "đóng vai" ký tự đầu của khối kế tiếp $F_{idx+1}$. Các bạn thử nháp với $k = 4$ ($F_3$ + 1 ký tự, idx = 3 lẻ → 'a': baba… ✔) hay $k = 9$ ($F_5$ + 1 ký tự, idx = 5 lẻ → 'a': bababbaba… ✔). Vậy:

Ký tự lẻ cuối cùng

Nếu sau vòng lặp còn $k = 1$ và idx (khối cuối cùng vừa lấy) là số lẻ thì ký tự đó là 'a' ⇒ cộng thêm 1. Còn nếu ngay từ đầu $k = 1$ thì chỉ là ký tự đầu của $F_n$: là 'a' khi $n$ chẵn.

Kiểm tra lại ví dụ đề: $(0, 1)$ → $n = 0$ chẵn → 1; $(1, 1)$ → lẻ → 0; $(3, 2)$ → lấy khối dài 2 ($F_2$, có 1 chữ a) → 1; $(7, 7)$ → khối 5 ($F_4$, 2 chữ a), còn 2 → khối 2 ($F_2$, 1 chữ a) → 3 ✔.

Để ý thú vị

Với $k \ge 2$ thì đáp án không phụ thuộc vào $n$ (chỉ cần $k \le |F_n|$), vì code chỉ dùng $k$. Nên ta có thể dùng chung bảng độ dài tới $F_{45}$ cho mọi test.

Minh hoạ: gom khối và so với xâu thật

Em nhập $n$ (nhỏ để còn vẽ được xâu) và $k$, bấm Tiếp để xem từng lần lấy khối. Phía trên là xâu $F_n$ thật với $k$ ký tự đầu được tô màu (vàng = 'a') để em đối chiếu kết quả:

n k

Ví dụ nhanh:

Source code giải theo tư tưởng ở trên (code này mình đã nộp thành công), các bạn xem để hiểu rõ hơn:

#include <bits/stdc++.h>
using namespace std;

int solve(int n, int k){
    if(k == 1){
        if(n % 2 == 0){
            return 1;
        }
        return 0;
    }
    int a[46], b[46];
    a[0] = a[1] = b[0] = 1;
    b[1] = 0;
    for(int i = 2; i <= 45; ++i){
        a[i] = a[i - 2] + a[i - 1];
        b[i] = b[i - 2] + b[i - 1];
    }
    int sum = 0;
    int idx;
    while(k >= 2){
        idx = upper_bound(a, a + 46, k) - a;
        idx--;
        sum += b[idx];
        k -= a[idx];
    }
    if(k == 1 && idx % 2 != 0){
        sum++;
    }
    return sum;
}

int main(){
    // freopen("FIB2.INP", "r", stdin);   // khi thi bằng file thì bỏ // ở 2 dòng này
    // freopen("FIB2.OUT", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n, k;
        cin >> n >> k;
        cout << solve(n, k) << endl;
    }
    return 0;
}

import sys
import bisect

def solve(n, k):
    if k == 1:
        if n % 2 == 0:
            return 1
        return 0
    a = [0] * 46
    b = [0] * 46
    a[0] = a[1] = b[0] = 1
    b[1] = 0
    for i in range(2, 46):
        a[i] = a[i - 2] + a[i - 1]
        b[i] = b[i - 2] + b[i - 1]
    sum_ = 0
    while k >= 2:
        idx = bisect.bisect_right(a, k) - 1
        sum_ += b[idx]
        k -= a[idx]
    if k == 1 and idx % 2 != 0:
        sum_ += 1
    return sum_

# sys.stdin = open("FIB2.INP", "r")   # khi thi bằng file thì bỏ # ở 2 dòng này
# sys.stdout = open("FIB2.OUT", "w")
input_data = sys.stdin.read().split()
it = iter(input_data)
t = int(next(it))
for _ in range(t):
    n = int(next(it))
    k = int(next(it))
    print(solve(n, k))

C++▶ Chạy tay từng dòng codeCách 2: tính sẵn độ dài a[] và số chữ 'a' b[] của F0..F45, rồi gom khối dài nhất ≤ k.

Dữ liệu vào (stdin) – sửa thoải mái4 0 1 1 1 3 2 7 7

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4int solve(int n, int k){

5 if(k == 1){

6 if(n % 2 == 0){

7 return 1;

8 }

9 return 0;

10 }

11 int a[46], b[46];

12 a[0] = a[1] = b[0] = 1;

13 b[1] = 0;

14 for(int i = 2; i <= 45; ++i){

15 a[i] = a[i - 2] + a[i - 1];

16 b[i] = b[i - 2] + b[i - 1];

17 }

18 int sum = 0;

19 int idx;

20 while(k >= 2){

21 idx = upper_bound(a, a + 46, k) - a;

22 idx--;

23 sum += b[idx];

24 k -= a[idx];

25 }

26 if(k == 1 && idx % 2 != 0){

27 sum++;

28 }

29 return sum;

30}

31

32int main(){

33 // freopen("FIB2.INP", "r", stdin); // khi thi bằng file thì bỏ // ở 2 dòng này

34 // freopen("FIB2.OUT", "w", stdout);

35 ios::sync_with_stdio(0);

36 cin.tie(0);

37 cout.tie(0);

38 int t;

39 cin >> t;

40 while(t--){

41 int n, k;

42 cin >> n >> k;

43 cout << solve(n, k) << endl;

44 }

45 return 0;

46}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: chỉ 2 mảng 46 phần tử ⇒ $O(1)$ (cỡ 45).
• Thời gian: mỗi test tính bảng mất 45 bước; vòng gom khối mỗi lần lấy khối dài nhất $\le k$ thì phần còn lại nhỏ hơn khối kế tiếp nên số lần lặp không quá ~45, mỗi lần upper_bound tốn $O(\log 46)$. Tổng cộng $O(T \cdot 45)$ – chạy tức thì.

Không gian$O(45)$

Thời gian$O(T \cdot 45)$

Có tràn int không?

$a[45] = 1\,836\,311\,903 \lt 2^{31} - 1 = 2\,147\,483\,647$ nên dùng int vẫn an toàn. Nhưng nếu đề nới lên $n = 46$ thì độ dài vượt int, lúc đó nhớ đổi sang long long nha.

Ghi chú của mình: code C++ và Python của cách 2 đã được kiểm tra với toàn bộ các cặp $(n, k)$ có $n \le 24$ (gần 200 nghìn cặp, so với đếm trực tiếp trên xâu thật) và thêm 1000 cặp ngẫu nhiên với $n$ tới 45 (so với một hàm đệ quy đếm chính xác) – khớp hết; 100 test $n = 45$, $k = |F_{45}|$ chạy chưa tới 0.1 giây. Code cách 1 cũng cho kết quả đúng với $n$ nhỏ, nhưng với $n = 45$ và giới hạn 256 MB thì bị lỗi cấp phát bộ nhớ ngay (đúng là MLE). Mình có sửa nhỏ ở cách 1: mảng xâu khai báo n + 2 phần tử thay vì n + 1, vì với test $n = 0$ của đề thì f[1] = "b" sẽ ghi ra ngoài mảng.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇