Hướng dẫn giải của [200 đề thầy Đức] Bài 94: Tìm số nhỏ nhất
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
Tìm số nguyên dương nhỏ nhất có đúng $d$ chữ số và tổng các chữ số bằng $s$. Nếu không tồn tại thì in $-1$. Ví dụ $s = 9, d = 2$ cho $18$; $s = 20, d = 3$ cho $299$; $s = 63, d = 3$ không tồn tại vì $3$ chữ số có tổng tối đa là $27$.
Sub 1: Vét cạn — ~O(10^d)~, dùng khi ~d \le 5~
Duyệt lần lượt các số có $d$ chữ số từ $10^{d-1}$ đến $10^d - 1$, và lấy số đầu tiên có tổng chữ số bằng $s$.
Kết quả chạy riêng sub này: đúng 11/21 test (10 test còn lại có $d$ lớn hơn miền của sub này).
Sub 2: Tham lam từ trái sang phải — ~O(d)~
Với mỗi vị trí từ trái sang phải, chọn chữ số nhỏ nhất có thể sao cho phần tổng còn lại không vượt quá $9 \cdot (\text{số vị trí còn lại})$. Chữ số đầu tiên phải từ $1$ trở lên (vì số có đúng $d$ chữ số). Nếu $s > 9d$ thì không có đáp án.
Bẫy cần chú ý: chỉ cần kiểm tra cả hai điều kiện: tổng còn lại không âm và không vượt quá khả năng của các vị trí còn lại.
Chương trình hoàn chỉnh
Chương trình đọc $T$ bộ dữ liệu. Nếu mọi $d \le 5$ thì gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int T;
vector<int> S, D; // mỗi bộ dữ liệu: tổng s và số chữ số d
// Sub 1: vét cạn — thử lần lượt các số có d chữ số (từ 10^(d-1) đến 10^d - 1),
// lấy số đầu tiên có tổng chữ số bằng s. Dùng khi mọi d <= 5
void sub1() {
for (int t = 0; t < T; t++) {
int s = S[t], d = D[t];
long long lo = 1, hi = 1, start = 1;
for (int i = 0; i < d; i++) hi *= 10; // hi = 10^d
for (int i = 1; i < d; i++) start *= 10; // start = 10^(d-1)
long long ans = -1;
for (long long x = max(lo, start); x < hi; x++) {
int sum = 0;
for (long long y = x; y > 0; y /= 10) sum += y % 10;
if (sum == s) { ans = x; break; }
}
cout << ans << "\n";
}
}
// Sub 2: chọn từng chữ số từ trái sang phải, mỗi lần chọn chữ số nhỏ nhất có thể.
// Chữ số đầu phải >= 1 (đủ d chữ số). Phần tổng còn lại không vượt quá 9 * (số vị trí còn lại).
// O(d * 10) cho mỗi bộ dữ liệu.
void sub2() {
for (int t = 0; t < T; t++) {
int s = S[t], d = D[t];
if (s > 9 * d) { cout << -1 << "\n"; continue; }
long long res = 0;
int rem = s;
bool ok = true;
for (int i = 0; i < d; i++) {
int lo = (i == 0) ? 1 : 0; // chữ số đầu không được là 0
int chosen = -1;
for (int dig = lo; dig <= 9; dig++) {
int left = d - i - 1; // số vị trí còn lại sau vị trí i
if (rem - dig >= 0 && rem - dig <= 9 * left) { chosen = dig; break; }
}
if (chosen < 0) { ok = false; break; }
res = res * 10 + chosen;
rem -= chosen;
}
cout << (ok ? res : -1) << "\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> T;
S.resize(T);
D.resize(T);
bool small = true;
for (int t = 0; t < T; t++) {
cin >> S[t] >> D[t];
if (D[t] > 5) small = false;
}
if (small) sub1(); // d nhỏ: vét cạn
else sub2(); // d lớn: tham lam O(d)
return 0;
}
Bình luận