Hiểu bài toán

Bài toán giả lập hệ thống cảnh báo và cấm người dùng của một diễn đàn dựa trên tốc độ nhắn tin.

• Input: Số lượng người dùng T, với mỗi người dùng cung cấp hai số nguyên N (số tin nhắn) và A (số giây).
• Output: Xác định trạng thái của người dùng dựa trên quy tắc:
  • Ban: Nếu nhắn quá 2 tin/giây (tức là N > 2 * A).
  • Warn: Nếu nhắn quá 1 tin/giây nhưng không đến 2 tin/giây (tức là N > A và N <= 2 * A).
  • None: Nếu nhắn không quá 1 tin/giây (tức là N <= A).
• Constraints: T lên tới 100,000, N và A có thể lên tới 10^10. Do đó, cần sử dụng biến số nguyên lớn (64-bit) và thuật toán hiệu quả O(1) cho mỗi test case.

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

Cách Phân loại trực tiếp

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while(t--) {
        long long n, a;
        cin >> n >> a;

        // Kiểm tra điều kiện
        if (n > 2 * a) {
            cout << "Ban" << "\n";
        } else if (n > a) {
            cout << "Warn" << "\n";
        } else {
            cout << "None" << "\n";
        }
    }
    return 0;
}

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

Đây là cách tiếp cận trực tiếp và hiệu quả nhất. Với mỗi người dùng, ta chỉ cần thực hiện các phép so sánh đơn giản:

1. Kiểm tra xem N có lớn hơn 2 * A không. Nếu có, in ra "Ban".
2. Nếu không, kiểm tra xem N có lớn hơn A không. Nếu có, in ra "Warn".
3. Nếu cả hai đều sai, in ra "None".

Vì N và A có thể lên tới 10^10, ta phải khai báo biến kiểu long long (hoặc int64_t) để tránh tràn số. Độ phức tạp thời gian là O(T) và bộ nhớ là O(1).

Cách Sử dụng hàm phụ

#include <iostream>
#include <string>

std::string check_spam(int N, int A) {
    if (N > 2 * A) {
        return "Ban";
    } else if (N > A) {
        return "Warn";
    } else {
        return "None";
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int T;
    std::cin >> T;
    for (int i = 0; i < T; ++i) {
        int N, A;
        std::cin >> N >> A;
        std::string result = check_spam(N, A);
        std::cout << result << '\n';
    }
    return 0;
}

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

Cách tiếp cận này tương tự về logic nhưng tách biệt việc xử lý logic vào một hàm check_spam. Về cơ bản, hiệu năng tương đương với cách tiếp cận trực tiếp. Tuy nhiên, giải pháp gốc được cung cấp có lỗi cú pháp nhỏ (thiếu #include <string> và lỗi тип int thay vì long long cho N, A). Logic vẫn là so sánh N với các ngưỡng A và 2*A.

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

Bài học kinh nghiệm

• Bài toán là một dạng xử lý điều kiện (conditional logic) đơn giản.
• Cần chú ý đến giới hạn dữ liệu (10^10), đòi hỏi phải dùng kiểu dữ liệu 64-bit (long long trong C++).
• Thứ tự kiểm tra điều kiện rất quan trọng: kiểm tra Ban (nặng nhất) trước, sau đó đến Warn, cuối cùng là None.

Lỗi thường gặp

• Sử dụng kiểu int (32-bit) gây tràn số khi A hoặc N lớn hơn 2 tỷ, dẫn đến kết quả tính toán sai (ví dụ: 2 * A bị tràn số âm).
• Quên các ký tự xuống dòng cần thiết ở đầu ra.
• So sánh sai thứ tự: Ví dụ Ban khi N/A >= 2 (tức là N >= 2*A), nhưng đề bài ghi "quá" (tức là >).