Tóm tắt đề bài

Cho một xâu ký tự (gồm chữ cái latin và chữ số) độ dài không quá \(10^6\). Trong xâu có thể xuất hiện nhiều đoạn liên tiếp các chữ số, mỗi đoạn được hiểu là một số nguyên không âm. Hãy tính tổng các số đó.

• Nếu xâu không chứa bất kỳ chữ số nào, in ra -1.

Ví dụ: ktab3b6afh12 có các số là \(3\), \(6\), \(12\) nên tổng là \(21\).

Phân tích

• Độ dài xâu tối đa \(10^6\) nên cần thuật toán \(O(n)\) duyệt một lần.
• Các số trong xâu được tạo bởi các chữ số liên tiếp:
  • Khi gặp chữ số, ta đang “xây” số hiện tại.
  • Khi gặp chữ cái (hoặc hết xâu), nếu đang có số thì “chốt” số đó vào tổng.
• Pitfall thường gặp:
  • Quên cộng nốt số ở cuối xâu (nếu xâu kết thúc bằng chữ số).
  • Trường hợp không có chữ số nào: phải in -1.
• Về kiểu dữ liệu:
  • Đề bài ghi “mỗi số không quá …” (bị thiếu trong statement), vì vậy để an toàn nên dùng kiểu 64-bit (\(long\ long\)) cho tổng và số đang xây.

Hướng giải quyết

Nhận xét

Ta có thể mô phỏng quá trình đọc xâu như đọc một biểu thức có các “token số” xen kẽ chữ:

• Nếu ký tự hiện tại là chữ số d:
  • Cập nhật số đang xây: \(cur = cur \times 10 + d\).
  • Đánh dấu đã từng gặp chữ số.
• Nếu ký tự hiện tại không phải chữ số:
  • Nếu đang ở trong một đoạn số, cộng \(cur\) vào tổng rồi đặt lại \(cur = 0\).

Thuật toán

1. Đọc xâu \(s\).
2. Khởi tạo:
   • sum = 0
   • cur = 0
   • inNumber = false (đang ở trong một đoạn số hay không)
   • hasDigit = false (đã gặp chữ số nào chưa)
3. Duyệt từng ký tự c trong \(s\):
   • Nếu c là chữ số:
     • hasDigit = true
     • inNumber = true
     • cur = cur * 10 + (c - '0')
   • Ngược lại (là chữ cái):
     • Nếu inNumber == true:
       • sum += cur
       • cur = 0, inNumber = false
4. Sau vòng lặp, nếu inNumber == true thì cộng nốt cur vào sum.
5. Nếu hasDigit == false in -1, ngược lại in sum.

Độ phức tạp

• Thời gian: \(O(n)\) với \(n\) là độ dài xâu (duyệt đúng một lần).
• Bộ nhớ: \(O(1)\) (không tính bộ nhớ lưu xâu đầu vào).

Code tham khảo

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    if (!getline(cin, s)) return 0;

    long long sum = 0;
    long long cur = 0;
    bool inNumber = false;
    bool hasDigit = false;

    for (char c : s) {
        if (c >= '0' && c <= '9') {
            hasDigit = true;
            inNumber = true;
            cur = cur * 10 + (c - '0');
        } else {
            if (inNumber) {
                sum += cur;
                cur = 0;
                inNumber = false;
            }
        }
    }

    // Chốt số nếu xâu kết thúc bằng chữ số
    if (inNumber) sum += cur;

    if (!hasDigit) cout << -1;
    else cout << sum;

    return 0;
}