Tóm tắt đề bài

Cho xâu \(S\) gồm chữ cái tiếng Anh và chữ số 0–9. Một “số” trong xâu là một đoạn liên tiếp các chữ số nhưng không chứa các chữ số 0 vô nghĩa ở đầu (tức là khi gặp một đoạn chữ số, ta bỏ các 0 đầu đoạn; nếu toàn 0 thì số là \(0\)).

Hãy tìm số chính phương lớn nhất xuất hiện trong các số tách được từ \(S\). Nếu không có số chính phương nào, in ra \(-1\).

Phân tích

• \(|S| \le 10^5\).
• Đề đảm bảo mỗi đoạn chữ số sau khi bỏ 0 đầu đoạn có không quá \(18\) chữ số có nghĩa, nên giá trị số có thể chứa trong kiểu \(64\)-bit (tối đa gần \(10^{18}\)).
• Ta cần:
  • Tách các đoạn chữ số liên tiếp trong \(S\).
  • Chuẩn hoá theo quy tắc “không có 0 vô nghĩa”:
    • Bỏ các 0 ở đầu đoạn.
    • Nếu bỏ hết (đoạn toàn 0) thì số là \(0\).
  • Kiểm tra số có phải chính phương: với \(x \le 10^{18}\) có thể dùng căn bậc hai nguyên (\(r=\lfloor\sqrt{x}\rfloor\)) rồi kiểm \(r^2=x\) hoặc \((r+1)^2=x\) để tránh sai số do double.

Bẫy hay gặp

• Đoạn như 00132 phải hiểu là số \(132\), không phải \(132\) và cũng không tính \(0\) ở đầu như một số riêng.
• Đoạn toàn 0 như 000 tạo ra số \(0\) (và \(0\) là số chính phương).
• Tránh tràn số khi bình phương: dùng __int128 khi tính \(r^2\).

Hướng giải quyết

Nhận xét

• Ta chỉ cần duyệt một lần qua xâu, gom các đoạn chữ số.
• Với mỗi đoạn chữ số, ta bỏ 0 đầu đoạn để lấy phần “có nghĩa” (tối đa \(18\) chữ số), chuyển sang số nguyên \(64\)-bit.
• Kiểm tra chính phương bằng căn bậc hai nguyên là đủ nhanh vì số lượng đoạn chữ số tối đa cũng chỉ \(O(|S|)\).

Thuật toán

1. Đặt ans = -1.
2. Duyệt i từ \(0\) đến \(|S|-1\):
   • Nếu S[i] không phải chữ số: tăng i.
   • Nếu là chữ số:
     1. Xác định đoạn chữ số liên tiếp \(S[i..j-1]\) (j là vị trí đầu tiên không phải chữ số).
     2. Trong đoạn đó, bỏ các 0 ở đầu:
        • Tìm k là vị trí đầu tiên trong \([i, j)\) sao cho S[k] != '0'.
        • Nếu không có (k == j) thì giá trị số là \(x = 0\).
        • Ngược lại, đọc số từ S[k..j-1] thành unsigned long long (độ dài \(\le 18\) theo đề).
     3. Kiểm tra \(x\) có là chính phương:
        • Tính \(r = \lfloor \sqrt{x} \rfloor\) (dùng long double).
        • Điều chỉnh và kiểm bằng __int128:
          • Nếu \(r^2 = x\) hoặc \((r+1)^2 = x\) thì \(x\) là chính phương.
     4. Nếu là chính phương: ans = max(ans, x).
     5. Gán i = j để tiếp tục.
3. In ans.

Độ phức tạp

• Thời gian: \(O(|S|)\), mỗi ký tự được xử lý hằng số lần.
• Bộ nhớ: \(O(1)\) (không tính bộ nhớ lưu xâu).

Code tham khảo

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

using ull = unsigned long long;
using i128 = __int128_t;

static bool isDigit(char c) {
    return c >= '0' && c <= '9';
}

static bool isPerfectSquare(ull x) {
    // sqrtl cho long double để giảm sai số với số lớn
    ull r = (ull) sqrtl((long double)x);

    auto sq = [&](ull t) -> i128 {
        return (i128)t * (i128)t;
    };

    if (sq(r) == (i128)x) return true;
    if (sq(r + 1) == (i128)x) return true;
    return false;
}

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

    string S;
    if (!(cin >> S)) return 0;

    long long ans = -1;

    int n = (int)S.size();
    int i = 0;
    while (i < n) {
        if (!isDigit(S[i])) {
            ++i;
            continue;
        }

        int j = i;
        while (j < n && isDigit(S[j])) ++j; // đoạn chữ số [i, j)

        // Bỏ các '0' vô nghĩa đầu đoạn
        int k = i;
        while (k < j && S[k] == '0') ++k;

        ull x = 0;
        if (k == j) {
            // toàn '0' => số 0
            x = 0;
        } else {
            // đọc số có nghĩa (đề đảm bảo <= 18 chữ số)
            for (int t = k; t < j; ++t) {
                x = x * 10 + (S[t] - '0');
            }
        }

        if (isPerfectSquare(x)) {
            ans = max(ans, (long long)x);
        }

        i = j; // nhảy qua đoạn chữ số
    }

    cout << ans << "\n";
    return 0;
}