Hướng dẫn giải của Tạo số (Đề tuyển sinh 10 Chuyên Quảng Trị 2024-2025)


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Hướng dẫn giải

Xâu ~S~ có ~|S| \le 100~ ký tự. Mỗi ký tự cho ra đúng một chữ số tiếp theo, nên số ~N~ luôn có ~|S|+1~ chữ số. Vì độ dài cố định, số nhỏ nhất là số có chữ số đầu nhỏ nhất hợp lệ.

Sub 1: Vét cạn — ~O(9 \cdot |S|)~, dùng khi ~|S| \le 100~

Thử lần lượt cả 9 chữ số đầu ~d = 1 \ldots 9~. Với mỗi ~d~, đi theo xâu: dấu + thì cộng 1, dấu - thì trừ 1, dấu = thì giữ nguyên. Nếu có chữ số nào ra ngoài đoạn ~[0, 9]~ thì cách này không hợp lệ. Lấy xâu chữ số nhỏ nhất trong các cách hợp lệ. Nếu chỉ nộp sub này: đúng 10/10 test.

Sub 2: Chọn chữ số đầu nhỏ nhất — ~O(|S|)~

Thử ~d = 1, 2, \ldots~ theo thứ tự tăng dần. Chữ số đầu nhỏ nhất hợp lệ cho ra ngay số nhỏ nhất, nên dừng ở cách đầu tiên tìm được. Bẫy cần chú ý: không được chọn chữ số đầu là 0; và cần kiểm tra mọi chữ số trung gian, không chỉ chữ số cuối. Nếu chỉ nộp sub này: đúng 10/10 test.

Chương trình hoàn chỉnh

Đề chỉ có một miền dữ liệu (~|S| \le 100~), nên main gọi sub1 trong mọi trường hợp; sub2 vẫn đúng nếu sau này đề cho xâu dài hơn. Đầu main có freopen vì máy chấm đọc/ghi file CAU2.INP, CAU2.OUT.

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

string s;   // xau S chi gom '+', '-', '='

// Thu chu so dau la d (1..9). Tra ve xau cac chu so neu hop le, neu khong tra ve "" .
string build(int d) {
    string res;
    int cur = d;
    res += char('0' + cur);
    for (char c : s) {
        if (c == '+') cur++;
        else if (c == '-') cur--;
        // '=' : giu nguyen
        if (cur < 0 || cur > 9) return "";   // ra ngoai chu so thi khong hop le
        res += char('0' + cur);
    }
    return res;
}

// Sub 1: vet can - thu ca 9 chu so dau, lay xau nho nhat trong cac xau hop le
void sub1() {
    string best = "";
    for (int d = 1; d <= 9; d++) {
        string t = build(d);
        if (t.empty()) continue;
        if (best.empty() || t < best) best = t;
    }
    if (best.empty()) cout << 0 << "\n";
    else cout << best << "\n";
}

// Sub 2: chu so dau nho nhat hop le cho ra ngay so nho nhat (do do dai N co dinh)
void sub2() {
    for (int d = 1; d <= 9; d++) {
        string t = build(d);
        if (!t.empty()) {
            cout << t << "\n";
            return;
        }
    }
    cout << 0 << "\n";
}

int main() {
    freopen("CAU2.INP", "r", stdin);     // may cham doc/ghi file
    freopen("CAU2.OUT", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> s;
    // Xau ngan (<= 100 ky tu): sub1 vet can cho chac
    // Xau dai: sub2 (chon chu so dau nho nhat hop le la xong)
    if (s.size() <= 100) sub1();
    else sub2();
    return 0;
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.