Hiểu bài toán

Cho một số nguyên dương N (3 ≤ N ≤ 10^9). Yêu cầu tìm ba số nguyên a, b, c sao cho a + b + c = N và a, b, c khác nhau (pairwise distinct). Để được 100% điểm, các số này phải khác nhau hoàn toàn. Nếu chỉ có 1 cặp bằng nhau (ví dụ a=b≠c), bạn chỉ được 50% điểm.

Ví dụ: Với N=5, ta có thể chọn a=0, b=2, c=3 vì 0+2+3=5 và 0, 2, 3 đều khác nhau.

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

Cách Xử lý c cứng (Hardcoded)

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

int main() {
    long long N;
    cin >> N;

    if (N == 4) {
        cout << "0 1 3";
    } else {
        cout << "0 2 " << N - 2;
    }

    return 0;
}

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

Phương pháp này dựa trên quan sát trực tiếp để đảm bảo 3 số phân biệt.

• Nếu N = 4: Ta không thể dùng bộ ba (0, 1, 3) vì 0+1+3=4 (hợp lệ) nhưng solution code in ra 0 1 3. Thực ra 0+1+3=4, và các số 0,1,3 đều khác nhau. Đây là một trường hợp đặc biệt để đảm bảo độ dài.
• Các trường hợp khác (N > 4): Tác giả chọn a=0, b=2, c=N-2.
  • Kiểm tra tổng: 0 + 2 + (N-2) = N.
  • Kiểm tra tính phân biệt:
    • a = 0, b = 2 (khác nhau).
    • a = 0, c = N-2. Vì N > 4, N-2 > 2, nên N-2 ≠ 0.
    • b = 2, c = N-2. Vì N > 4, N-2 > 2, nên N-2 ≠ 2.
  • Kết luận: Ba số luôn phân biệt.
• Code này bỏ qua trường hợp N=3 (vì N≥3). Nếu N=3, N-2=1, bộ ba (0,2,1) t tổng bằng 3 và phân biệt. Tuy nhiên N=3 là biên.

Cách Phương pháp khai báo biến

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

int main() {
    long long N;
    cin >> N;
    cout << 0 << " " << 1 << " " << N - 1;
    return 0;
}

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

Đây là cách tiếp cận đơn giản hóa, in ra bộ ba (0, 1, N-1).

• Kiểm tra tổng: 0 + 1 + (N-1) = N.
• Kiểm tra tính phân biệt:
  • a = 0, b = 1 (khác nhau).
  • a = 0, c = N-1. Nếu N = 1 thì N-1=0, nhưng N ≥ 3 nên N-1 ≥ 2 (khác 0).
  • b = 1, c = N-1. Nếu N = 2 thì N-1=1, nhưng N ≥ 3 nên N-1 ≥ 2 (khác 1).
• Lỗ hổng: Nếu N = 2 (ra trường hợp N=2), bộ ba (0, 1, 1) sẽ có hai số bằng nhau. Tuy nhiên đề bài ghi N ≥ 3, nên với N=3, ta có (0, 1, 2) đều khác nhau. Với N=4, ta có (0, 1, 3) đều khác nhau.
• Phương pháp này sinh ra 100% điểm cho N≥3.

Cách Phương pháp số âm

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

int main() {
    long long n;
    if (!(cin >> n)) return 0;
    cout << -1 << " " << 0 << " " << (n + 1) << "\n";
    return 0;
}

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

Phương pháp này sử dụng một số âm để tạo ra bộ ba phân biệt.

• Bộ ba: a = -1, b = 0, c = n + 1.
• Kiểm tra tổng: -1 + 0 + (n + 1) = n.
• Kiểm tra tính phân biệt:
  • a = -1, b = 0 (khác nhau).
  • a = -1, c = n + 1. Vì n ≥ 3, n+1 ≥ 4, nên n+1 ≠ -1.
  • b = 0, c = n + 1. Vì n ≥ 3, n+1 ≥ 4, nên n+1 ≠ 0.
• Kết luận: Ba số luôn phân biệt.
• Lưu ý: Đề bài yêu cầu 'số nguyên', không giới hạn số dương, nên số âm là hợp lệ.

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

Bài học kinh nghiệm

• Vì N ≥ 3, ta luôn có thể tìm các số nguyên a, b, c phân biệt sao cho tổng bằng N.
• Một số bộ ba 'cơ bản' luôn hoạt động cho N đủ lớn là (0, 1, N-1), (-1, 0, N+1), hoặc (0, 2, N-2).
• Cần lưu ý các trường hợp biên nhỏ (ví dụ N=3, N=4) để đảm bảo các số phân biệt.

Lỗi thường gặp

• Sử dụng các bộ ba cố định không kiểm tra kỹ điều kiện N (ví dụ (0, 1, N-1) có thể sinh ra 1 nếu N=2). May mắn thay, N≥3.
• Quên kiểm tra các số bằng nhau (ví dụ N=2 với (0, 1, N-1) sẽ thành (0, 1, 1)).
• Giả sử rằng a, b, c phải là số dương.