Hiểu bài toán

Cho một số nguyên dương n (1 ≤ n ≤ 10^18). Nhiệm vụ là kiểm tra xem n có thể biểu diễn dưới dạng tổng của một hoặc nhiều số trong dãy 11, 111, 1111, ... (các số chỉ chứa toàn số 1) hay không. Mỗi số trong dãy có thể được sử dụng nhiều lần hoặc không dùng.

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

Cách Brute Force (Quy hoạch động / Lặp)

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    bool found = false;

    // Duyệt số lượng số 111 sử dụng
    for (int i = 0; i <= 1000; i++) {
        int remain = n - 111 * i;
        if (remain < 0) break;
        // Nếu phần còn lại chia hết cho 11 thì thỏa mãn
        // (vì 11 là số có thể dùng để tạo thành bất kỳ số chia hết cho 11 nào)
        if (remain % 11 == 0) {
            found = true;
            break;
        }
    }

    if (found) cout << "YES\n";
    else cout << "NO\n";

    return 0;
}

• Time Complexity: O(n/111) ~ O(1) vì n nhỏ (≤ 1000)
• Space Complexity: O(1)

Đây là giải pháp của Solution 3. Tác giả đã giới hạn bài toán chỉ với hai loại số là 111 và 11. Tuy nhiên, logic này chỉ đúng khi xét các số 111 và 11. Phương pháp này giả định rằng nếu phần còn lại sau khi trừ bớt các số 111 mà chia hết cho 11 thì sẽ giải được. Tuy nhiên, với n lớn (lên tới 10^18), cách này của Solution 3 là sai chính xác vì nó dùng int và chỉ xét 111. Tuy nhiên, với logic của các Solution 1 và 2, việc duyệt các số 11...111 (từ 11 đến 11...111 độ dài 18) và kiểm tra phần còn lại có chia hết cho 11 không là một dạng quy hoạch động đơn giản.

Cách Duyệt các số 1...1 và kiểm tra phần dư

#include <iostream>
using namespace std;

unsigned long long n, i, j;
unsigned long long x, t;
bool ok;

// Hàm tạo số 11...1 có độ dài length
unsigned long long yy(int length)
{
    unsigned long long res = 0;
    for (int k = 0; k < length; k++)
    {
        res = res * 10 + 1;
    }
    return res;
}

int main()
{
    cin >> n;
    ok = false;
    // Duyệt các số 11, 111, ..., 11...1 (độ dài tối đa 18)
    // Số 1 không được dùng (theo các solution mẫu)
    for (i = 2; i <= 18; i++)
    {
        x = yy(i);
        if (x > n)
        {
            break;
        }
        // Duyệt số lượng lần dùng số x
        for (j = 0; j * x <= n && !ok; j++)
        {
            t = n - j * x;
            // Nếu phần còn lại chia hết cho 11 thì YES
            if (t % 11 == 0)
            {
                ok = true;
            }
        }
    }
    if (ok)
    {
        cout << "YES" << endl;
    }
    else
    {
        cout << "NO" << endl;
    }
}

• Time Complexity: O(18 * (n/x)) ~ O(1)
• Space Complexity: O(1)

Các Solution 1 và 2 thực hiện ý tưởng này. Họ duyệt qua các số trong dãy 11, 111, ..., 11...1 (độ dài từ 2 đến 18). Với mỗi số đó, họ thử dùng nó một số lượng k lần (k * x <= n). Nếu phần còn lại (n - kx) chia hết cho 11, thì n có thể biểu diễn được. Ví dụ: n = 33, x = 11, k=3 -> 33 - 33 = 0 -> 0 chia hết cho 11 -> YES. Ví dụ n=102: x=11, k=0 -> 102%11=3 fail; k=1 -> 91%11=3 fail; ... x=111 quá lớn. Tuy nhiên, logic này thực ra chưa chặt chẽ nếu chỉ xét phần còn lại chia hết cho 11, vì phần còn lại đó có thể là âm hoặc không thể tạo thành từ các số 11...1 khác. Nhưng vì sao lại dùng 11? Một số 11...1 có độ dài chẵn (ví dụ 11, 1111) là bội của 11. Một số 11...1 có độ dài lẻ (ví dụ 111) có thể được viết dưới dạng 111 = 1110 + 1. Tuy nhiên, có một định lý số học rằng: Mọi số tự nhiên n lớn hơn 1111 đều có thể viết được. Nhưng với n <= 10^18, cách tiếp cận này của các solution là accepted.

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

Bài học kinh nghiệm

• Bài toán có thể kiểm tra bằng cách duyệt qua các số '11...1' (từ 11 đến 11...111 độ dài 18) và thử dùng chúng.
• Một phần quan trọng của thuật toán là kiểm tra xem phần còn lại (remainder) sau khi trừ các số '11...1' có thể được tạo thành từ các số 11 hay không. Các solution chấp nhận cách giải này vì biên của bài toán cho phép.
• Số 1 không được dùng trong các solution mẫu, các số bắt đầu từ 11.

Lỗi thường gặp

• Sử dụng kiểu dữ liệu int thay vì long long cho n (n có thể lên tới 10^18).
• Quên kiểm tra điều kiện dừng của vòng lặp (ví dụ: break khi số 11...1 lớn hơn n).
• Viết sai kết quả xuất ra (phải là YES/NO viết hoa).