Hiểu bài toán

Bài toán yêu cầu kiểm tra xem ba số tự nhiên a, b, c và số k cho trước có tạo thành một 'bộ ba hoàn hảo' hay không. Theo định nghĩa, ba số được coi là hoàn hảo nếu khoảng cách giữa hai số bất kỳ trong chúng không vượt quá k. Nói cách khác, hiệu số giữa số lớn nhất và số nhỏ nhất trong bộ ba phải nhỏ hơn hoặc bằng k.

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

Cách Kiểm tra tất cả các cặp

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

int main() {
    long long a, b, c, k;
    cin >> a >> b >> c >> k;

    // Kiểm tra từng cặp số
    if (abs(a - b) <= k && abs(b - c) <= k && abs(c - a) <= k) {
        cout << "Yes";
    } else {
        cout << "No";
    }

    return 0;
}

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

Cách tiếp cận này kiểm tra trực tiếp điều kiện đề bài: khoảng cách giữa mọi cặp số phải không quá k. Ta tính hiệu số tuyệt đối của từng cặp (a-b), (b-c), (c-a) và so sánh với k. Nếu cả ba điều kiện đều thỏa mãn, in 'Yes'; ngược lại in 'No'. Cách này dễ hiểu và bám sát định nghĩa.

Cách Tối ưu bằng max/min

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

int main() {
    long long a, b, c, k;
    cin >> a >> b >> c >> k;

    long long max_val = max({a, b, c});
    long long min_val = min({a, b, c});

    if (max_val - min_val <= k) {
        cout << "Yes";
    } else {
        cout << "No";
    }

    return 0;
}

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

Đây là cách tiếp cận tối ưu nhất. Ta chỉ cần tìm số lớn nhất và số nhỏ nhất trong bộ ba. Nếu hiệu của chúng (khoảng cách lớn nhất) không vượt quá k, thì chắc chắn khoảng cách giữa bất kỳ hai số nào cũng không vượt quá k. Điều này đúng vì nếu max - min <= k, thì mọi hiệu số khác (ví dụ max - med, med - min) đều nhỏ hơn hoặc bằng max - min. Do đó, chỉ cần một phép so sánh duy nhất.

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

Bài học kinh nghiệm

• Bài toán có thể được đơn giản hóa bằng cách chỉ quan tâm đến hai số extreme (lớn nhất và nhỏ nhất) thay vì phải kiểm tra tất cả các cặp.
• Vì dữ liệu đầu vào là các số tự nhiên (không âm) và k cũng là số tự nhiên, ta có thể dùng phép trừ trực tiếp thay vì abs() khi đã biết thứ tự của max và min.

Lỗi thường gặp

• Lưu ý thứ tự nhập vào: một số giải pháp nhập sai thứ tự a, b, c, k (ví dụ nhập k trước), dẫn đến kết quả sai.
• Cần sử dụng kiểu dữ liệu đủ lớn (long long) để tránh tràn số nếu các đầu vào có giá trị lớn (lên đến 10^18), nhưng trong thực tế int cũng đủ dùng cho các giá trị nhỏ.