Hiểu bài toán

Bài toán yêu cầu đếm số lượng hoa (ký tự 'H') trong một chuỗi được tạo ra bằng cách ghép x ký tự a và y ký tự b. Tuy nhiên, chỉ xét một phần đầu của chuỗi này có độ dài z. Nói cách khác, ta cần đếm số lượng 'H' trong z ký tự đầu tiên của chuỗi S = a lặp x lần + b lặp y lần.

Input gồm 5 giá trị:

• x: số lần lặp ký tự a
• a: ký tự đầu tiên (ví dụ 'H' hoặc 'O')
• y: số lần lặp ký tự b
• b: ký tự thứ hai
• z: độ dài phần đầu cần xét

Output là một số nguyên thể hiện số lượng ký tự 'H' trong z ký tự đầu của chuỗi.

Ví dụ: x=3, a='H', y=2, b='O', z=4. Chuỗi S = HHHOO. 4 ký tự đầu là HHHO. Có 3 ký tự 'H'.

Các giải pháp nộp vào cho thấy bài toán này có thể được giải quyết bằng cách tính toán trực tiếp dựa trên logic số học thay vì tạo chuỗi, mặc dù giải pháp tạo chuỗi cũng đúng (nhưng tốn bộ nhớ và thời gian nếu x, y lớn).

Các cách tiếp cận

Cách Mô phỏng tạo chuỗi

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

int main() {
    freopen("sf.inp", "r", stdin);
    freopen("sf.out", "w", stdout);

    int x, y, z;
    char a, b;
    cin >> x >> a >> y >> b >> z;

    string s = "";
    for (int i = 0; i < x; i++) s += a;
    for (int i = 0; i < y; i++) s += b;

    int ans = 0;
    for (int i = 0; i < z; i++) {
        if (s[i] == 'H') ans++;
    }

    cout << ans;
    return 0;
}

• Time Complexity: O(x + y)
• Space Complexity: O(x + y)

Cách tiếp cận này mô phỏng chính xác những gì bài toán yêu cầu. Nó tạo ra chuỗi kết quả đầy đủ bằng cách nối x ký tự a và y ký tự b. Sau đó, nó duyệt qua z ký tự đầu tiên của chuỗi để đếm số lượng 'H'.

• Ưu điểm: Dễ hiểu, cài đặt đơn giản, đúng với mô tả bài toán.
• Nhược điểm: Nếu x và y lớn (ví dụ $10^6$), việc tạo chuỗi sẽ tốn bộ nhớ và thời gian. Tuy nhiên, trong hầu hết các bài thi học sinh giỏi, dữ liệu thường cho phép cách này hoặc cách tối ưu hơn.

Cách Tính toán trực tiếp (Logic)

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

int main() {
    ifstream fin("sf.inp");
    ofstream fout("sf.out");

    int n, m, k;
    char c1, c2;
    fin >> n >> c1;
    fin >> m >> c2;
    fin >> k;

    int countH = 0;

    // Lấy hoa bắt đầu từ bên trái
    if (k <= n) {
        // Lấy hết bên trái nhưng chưa hết k
        if (c1 == 'H') countH = k;
        else countH = 0;
    } else {
        // Lấy hết bên trái và tiếp tục bên phải
        countH = (c1 == 'H') ? n : 0;
        int remaining = k - n;
        if (c2 == 'H') countH += remaining;
    }

    fout << countH << endl;

    fin.close();
    fout.close();
    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Đây là giải pháp tối ưu. Thay vì tạo chuỗi, ta chia vấn đề thành hai trường hợp dựa trên độ dài z so với x (số lượng ký tự phần đầu).

Trường hợp 1: z nhỏ hơn hoặc bằng x ($k \le n$).

• Toàn bộ z ký tự đều thuộc phần a.
• Nếu a là 'H', đáp án là z.
• Ngược lại, đáp án là 0.

Trường hợp 2: z lớn hơn x.

• Ta lấy hết x ký tự của phần a, sau đó lấy thêm (z - x) ký tự từ phần b.
• Đếm 'H' từ phần a: Nếu a là 'H', cộng x, cộng 0 nếu không.
• Đếm 'H' từ phần b: Nếu b là 'H', cộng thêm (z - x).

Cách này bỏ qua việc tạo chuỗi và chỉ sử dụng phép toán số học, chạy tức thời ngay cả với dữ liệu lớn.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán có thể được chia thành 2 trường hợp dựa trên việc z nằm hoàn toàn trong phần a hay đã tràn sang phần b.
• Chỉ cần quan tâm đến ký tự a và b là 'H' hay không, không cần quan tâm ký tự cụ thể nếu nó không phải 'H'.
• Giải pháp tính toán trực tiếp (O(1)) hiệu quả hơn nhiều so với giải pháp mô phỏng chuỗi (O(n)), đặc biệt khi dữ liệu lớn.

Lỗi thường gặp

• Quên kiểm tra điều kiện z > x khi tính toán phần b (ví dụ: lầm tưởng vẫn còn a để lấy).
• Sử dụng kiểu dữ liệu nhỏ (như int hoặc short) nếu x, y, z có thể lên tới $10^9$ (dù trong bài này int có thể đủ nhưng long long an toàn hơn).
• Lỗi nhập xuất: Quên freopen hoặc dùng cin/cout mà không tắt đồng bộ hóa với file (trong một số trường hợp đặc biệt).