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