B4185 [Giải thi đấu Trung Sơn 2024] Dãy con bội số

Mô tả bài toán

Cho một chuỗi số, hãy đếm số lượng các dãy con liên tục (substring) thỏa mãn điều kiện là bội số của 4 hoặc 5. Lưu ý rằng:

• Một dãy con có thể bắt đầu bằng chữ số 0.
• Hai dãy con được coi là khác nhau nếu chúng bắt đầu từ các vị trí khác nhau trong chuỗi.
• Một dãy con nếu đồng thời là bội số của 4 và 5 (ví dụ: bội số của 20) thì chỉ được đếm một lần.

Đầu vào

Một dòng chứa một chuỗi số có độ dài n.

Đầu ra

Một dòng chứa một số nguyên là số lượng dãy con thỏa mãn yêu cầu.

Ví dụ

Đầu vào:
04320

Đầu ra:
11

Giải thích

Các dãy con thỏa mãn trong ví dụ trên là: 0, 04, 0432, 04320, 4, 432, 4320, 32, 320, 20, 0.

Phân tích

Để giải quyết bài toán này, chúng ta cần tận dụng các quy tắc chia hết:

• Bội số của 5: Một số là bội số của 5 khi và chỉ khi chữ số cuối cùng của nó là 0 hoặc 5.
• Bội số của 4: Một số là bội số của 4 khi và chỉ khi hai chữ số cuối cùng của nó tạo thành một số chia hết cho 4.

Chúng ta có thể duyệt qua chuỗi và đếm số lượng dãy con thỏa mãn các điều kiện trên. Tuy nhiên, cần cẩn thận để không đếm trùng các dãy con là bội số của cả 4 và 5 (tức là bội số của 20). Một cách tiếp cận hiệu quả là sử dụng quy tắc chia hết để kiểm tra từng vị trí trong chuỗi: 1. Duyệt qua từng ký tự trong chuỗi. 2. Với mỗi ký tự, kiểm tra xem nó có phải là chữ số 0 hoặc 5 không. Nếu có, mọi dãy con kết thúc tại vị trí này đều là bội số của 5. 3. Với mỗi cặp ký tự liên tiếp, kiểm tra xem hai chữ số này có tạo thành một số chia hết cho 4 không. Nếu có, mọi dãy con kết thúc tại vị trí thứ hai của cặp này đều là bội số của 4. 4. Để tránh đếm trùng các dãy con là bội số của 20, chúng ta có thể đếm riêng các dãy con là bội số của 4, bội số của 5, và sau đó trừ đi số lượng dãy con là bội số của 20. Tuy nhiên, một cách đơn giản hơn là trong quá trình duyệt, chúng ta chỉ cần kiểm tra và đếm nếu dãy con thỏa mãn điều kiện của 4 HOẶC 5. Cách tiếp cận này cũng cho kết quả đúng.

Giải pháp

Chúng ta sẽ duyệt qua chuỗi từ đầu đến cuối. Với mỗi vị trí, chúng ta sẽ thực hiện các kiểm tra sau: 1. **Kiểm tra bội số của 5:** Nếu ký tự tại vị trí `i` là '0' hoặc '5', thì có đúng một dãy con (chính nó) kết thúc tại `i` là bội số của 5. 2. **Kiểm tra bội số của 4 (hai chữ số):** Nếu `i > 0`, chúng ta tạo số từ hai chữ số `s[i-1]` và `s[i]`. Nếu số này chia hết cho 4, thì có đúng một dãy con (hai chữ số này) kết thúc tại `i` là bội số của 4. 3. **Kiểm tra bội số của 4 (một chữ số):** Nếu ký tự tại vị trí `i` là '0', '4', hoặc '8', thì nó là một bội số của 4. Chúng ta sẽ sử dụng một biến đếm để tổng hợp kết quả. Lưu ý rằng cách tiếp cận này đảm bảo mỗi dãy con chỉ được đếm một lần vì chúng ta kiểm tra từng dãy con cụ thể (một chữ số hoặc hai chữ số).

Mã nguồn tham khảo (C++)

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s;
    cin >> s;
    long long result = 0;
    int n = s.length();

    for (int i = 0; i < n; ++i) {
        // Kiểm tra bội số của 5 (chữ số cuối là 0 hoặc 5)
        if (s[i] == '0' || s[i] == '5') {
            result++;
        }

        // Kiểm tra bội số của 4 (hai chữ số cuối)
        if (i > 0) {
            int two_digit_num = (s[i-1] - '0') * 10 + (s[i] - '0');
            if (two_digit_num % 4 == 0) {
                result++;
            }
        }

        // Kiểm tra bội số của 4 (một chữ số cuối)
        int last_digit = s[i] - '0';
        if (last_digit % 4 == 0) {
            result++;
        }
    }

    cout << result << endl;
    return 0;
}