Hiểu bài toán

Cho trước T câu hỏi. Với mỗi câu hỏi, cho một số nguyên dương N. Tìm số nguyên lớn nhất có đúng N chữ số (không có số 0 ở đầu) mà tích tất cả các chữ số của nó bằng 9 * 10^(N-2). Ví dụ: Với N=2, ta cần số 2 chữ số có tích chữ số là 9 * 10^(0) = 9. Số 81 có tích là 8*1=8 (sai), nhưng chú ý đề bài. Các solution in ra 999...890...01. Ví dụ N=2: 81. N=3: 9801. N=4: 998001. Ta cần tìm số lớn nhất.

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

Cách Xây dựng chuỗi theo quy luật

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    freopen("nine.inp","r",stdin);
    freopen("nine.out","w",stdout);

    int t;
    cin >> t;
    while (t--) {
        int b;
        cin >> b;

        if (b == 1) {
            cout << 81 << '\n';
            continue;
        }
        for (int i = 0; i < b-1; i++) cout << '9';
        cout << '8';
        for (int i = 0; i < b-1; i++) cout << '0';
        cout << '1' << '\n';
    }
}

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

Approach này dựa trên quan sát quy luật của các số thỏa mãn. Với N=2 là 81, N=3 là 9801, N=4 là 998001. Số đó có dạng: (N-1) số 9, theo sau là số 8, rồi (N-1) số 0, và kết thúc bằng số 1. Code duyệt để in ra các ký tự này. Với N=1, output là 81. Do tổng quan sát kỹ, N=1 có thể là trường hợp đặc biệt của quy luật này nếu coi N-1=0, nhưng output lại là 81 khác với quy luật 98...01. Solution check riêng N=1.

Cách Quy luật chuỗi (Refactored)

#include <bits/stdc++.h>
using namespace std;
#define taskname "nine"
void sol(int m)
{
    if (m == 0)
        return ;
    string r = "";
    if (m > 1)
        r.append(m - 1, '9');
    r += '8';
    if (m > 1)
        r.append(m - 1, '0');
    r += '1';
    cout << r << endl;
}
int main()
{
    if (fopen (taskname".inp","r"))
    {
        freopen (taskname".inp","r",stdin);
        freopen (taskname".out","w",stdout);
    }
    cin.tie(0)->sync_with_stdio(0);

    int k;
    cin >> k;

    while (k--)
    {
        int n;
        cin >> n;
        sol(n);
    }
    return 0;
}

• Time Complexity: O(T * N)
• Space Complexity: O(N)

Cách tiếp cận này dùng hàm sol để xử lý từng trường hợp. Nó xây dựng chuỗi kết quả bằng cách nối các chuỗi con. Logic tương tự Approach 1: tạo (N-1) ký tự '9', thêm '8', thêm (N-1) ký tự '0', thêm '1'. Việc dùng string và append giúp code dễ đọc hơn so với in từng ký tự.

Cách Quy luật chuỗi (Tối ưu)

#include <bits/stdc++.h>

using namespace std;

#define int long long

#define task "nine"

void pre () {
    freopen(task".inp", "r", stdin);
    freopen(task".out", "w", stdout);
}
/*_______________________SOLUTION IS HERE____________________________________*/

int tt;
signed  main() {
    pre();
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> tt; while (tt--) {
        int n; cin >> n;
        string s;
        if (n == 1) {
            cout << "81\n";
            continue;
        }
        s.append(max(0ll, n - 1), '9');
        s.push_back('8');
        s.append(max((0ll, n - 1), '0');
        s.push_back('1');
        cout << s << "\n";
    }
    return 0;
}

• Time Complexity: O(T * N)
• Space Complexity: O(N)

Đây là phiên bản chi tiết hơn của Approach 2, sử dụng string để lưu kết quả. Lưu ý rằng append(count, char) là cách hiệu quả để tạo chuỗi lặp lại. Code này cũng xử lý trường hợp N=1 riêng (output là 81). Dù độ phức tạp tương tự, việc dùng string thường dễ quản lý hơn là in trực tiếp từng ký tự nếu có thêm logic xử lý.

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

Bài học kinh nghiệm

• Bài toán có quy luật rất rõ ràng: Số kết quả là một số có dạng '9...980...01' với (N-1) số 9 và (N-1) số 0.
• Trường hợp N=1 là ngoại lệ so với quy luật chung này (output là 81 thay vì 81 theo quy luật 98...01 nếu áp dụng N-1=0).

Lỗi thường gặp

• Quên xử lý trường hợp N=1 riêng vì quy luật chung có thể không bao gồm nó.
• Lỗi tràn số nếu cố tính toán số nguyên lớn thay vì in chuỗi.