Hướng dẫn giải của Mật khẩu (đề HSG 12 Khánh Hòa 2020-2021)
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.
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 lớn nhất có đúng N chữ số và tổng các chữ số bằng S. N lên tới 10^4 nên không thể thử từng số; bài giải bằng cách tham lam.
Chỉ viết 1 sub vì với N lớn không có cách vét cạn khả thi (liệt kê các số N chữ số là quá nhiều). Đạt 20/20 test.
Sub 1: Tham lam từ trái sang phải — ~O(n)~
- Nếu S > 9N thì không tồn tại số thỏa mãn, in −1.
- Nếu S = 0: chỉ có số 0 là hợp lệ khi N = 1, các trường hợp khác in −1.
- Ngược lại, lần lượt với từng vị trí từ trái sang phải, chọn chữ số là min(9, phần tổng còn lại). Làm như vậy chữ số bên trái càng lớn càng tốt nên số tạo ra là lớn nhất. Chữ số đầu luôn khác 0 vì S ≥ 1.
Kết quả là xâu N chữ số nên in trực tiếp dưới dạng xâu.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("PASSWORD.INP", "r")) { freopen("PASSWORD.INP", "r", stdin); freopen("PASSWORD.OUT", "w", stdout); }
long long n, s;
cin >> n >> s;
// Tổng các chữ số tối đa là 9*N; quá thì không có mật khẩu
if (s > 9 * n) { cout << -1 << "\n"; return 0; }
// Trường hợp đặc biệt: S = 0 chỉ có số 0 (1 chữ số); N >= 2 không thể có số N chữ số có tổng 0
if (s == 0) {
if (n == 1) cout << 0 << "\n";
else cout << -1 << "\n";
return 0;
}
// Tham lam: để số lớn nhất thì chữ số bên trái càng lớn càng tốt, mỗi vị trí lấy min(9, phần còn lại)
string res;
long long rem = s;
for (long long i = 0; i < n; i++) {
int d = (int)min(9LL, rem);
res += char('0' + d);
rem -= d;
}
cout << res << "\n";
return 0;
}
Bình luận