[GCC TRAINING 2026 — BUỔI 4] Nam Anh Xuất Viện

[spoiler="Ý Tưởng (Hướng Dẫn Giải)"] - Bài toán yêu cầu ta kiểm tra $$$3$$$ điều kiện cho một số nguyên dương $$$x$$$: 1. $$$x$$$ là số nguyên tố. 2. Số đảo ngược của $$$x$$$ là số nguyên tố. 3. Tổng các chữ số của $$$x$$$ là số nguyên tố.

• Phân tách hàm (Modularity): Để code không bị rối, dễ quản lý biến và dễ debug, chúng ta BẮT BUỘC phải viết $$$3$$$ hàm con riêng biệt: kiemTraNguyenTo(n), daoNguocSo(n), và tongChuSo(n).

• Tối ưu thời gian (Chống bẫy TLE):

• Giới hạn $$$x \lt 10^9$$$. Nếu viết hàm kiểm tra nguyên tố bằng cách chạy vòng lặp từ $$$2$$$ đến $$$x-1$$$, độ phức tạp là $$$O(x) \approx 10^9$$$ phép toán. Chắc chắn sẽ bị Time Limit Exceeded (TLE).
• Cách giải quyết: Chỉ cần chạy vòng lặp đến $$$\sqrt{x}$$$ (tức là i * i <= n). Lúc này số phép toán giảm xuống chỉ còn $$$\approx 31622$$$, giúp code vượt qua các test lớn dễ dàng.

• Kỹ thuật cờ hiệu (Flag Optimization):

• Đề bài yêu cầu: Chỉ cần $$$1$$$ số sai là Nam Anh phải ở lại. Do đó, ta dùng một biến bool can_release = true.
• Trong lúc đọc dữ liệu, nếu phát hiện một số sai, ta gán can_release = false. Từ các số sau trở đi, ta vẫn phải đọc cin >> x (để hút cạn dữ liệu Input), nhưng không cần gọi hàm kiểm tra nữa để tiết kiệm tối đa thời gian chạy. Tránh trường hợp dính TLE oan uổng khi test case cố tình nhét một số sai ở đầu và $$$999$$$ số cực lớn ở phía sau! [/spoiler]

[spoiler="Code C++ Chuẩn"] ```cpp

include

using namespace std;

// Hàm 1: Kiểm tra số nguyên tố (tối ưu O(sqrt(n))) bool kiemTraNguyenTo(int n) { if (n < 2) return false; for (int i = 2; i * i <= n; i++) { if (n % i == 0) { return false; } } return true; }

// Hàm 2: Đảo ngược số int daoNguocSo(int n) { int res = 0; while (n > 0) { res = res * 10 + (n % 10); n /= 10; } return res; }

// Hàm 3: Tính tổng các chữ số int tongChuSo(int n) { int sum = 0; while (n > 0) { sum += (n % 10); n /= 10; } return sum; }

int main() { // Tối ưu I/O tốc độ cao ios_base::sync_with_stdio(false); cin.tie(NULL);

int t;
if (cin >> t) {
    bool can_release = true;

    for (int i = 0; i < t; i++) {
        int x;
        cin >> x;

        // Nếu đã phát hiện số sai trước đó, chỉ cin >> x chứ KHÔNG gọi hàm kiểm tra nữa
        if (can_release) {
            if (!kiemTraNguyenTo(x) || 
                !kiemTraNguyenTo(daoNguocSo(x)) || 
                !kiemTraNguyenTo(tongChuSo(x))) {
                can_release = false;
            }
        }
    }

    if (can_release) {
        cout << "RELEASED\n";
    } else {
        cout << "STAYING\n";
    }
}

return 0;

}