Hướng dẫn giải của MẬT KHẨU (CỤM BN3)
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ó ~N~ chữ số và tổng các chữ số bằng ~S~. Với độ dài cố định, số lớn nhất có chữ số lớn nhất đặt ở hàng cao nhất. Nếu ~S > 9N~ thì in -1.
Sub 1: tham lam từng chữ số — ~O(N)~
Bài rất đơn giản (một vòng lặp, mỗi chữ số là min(9, phần còn lại)), nên chỉ viết một sub. Đúng 12/12 test. Trường hợp ~S = 0~ với ~N = 1~ in 0; cần kiểm tra lại nếu đề gốc có ý khác.
Chương trình hoàn chỉnh
main đọc N và S, gọi sub1 (bài chỉ có một sub).
#include <bits/stdc++.h>
using namespace std;
// Tim so nguyen lon nhat co N chu so va tong cac chu so bang S.
// Voi do dai co dinh, muon so lon nhat thi uu tien chu so lon o hang cao.
// Tham lam: moi vi tri (tu trai sang) lay chu so lon nhat co the, tuc min(9, con lai).
// Bai rat don gian (mot vong lap), nen chi viet mot sub.
void sub1(long long N, long long S) {
// Khong co so nao co N chu so va tong S khi S = 0 (tru so 0 khi N = 1) hoac S > 9N
if (S > 9 * N || (S == 0 && N > 1)) {
cout << -1 << "\n";
return;
}
if (S == 0) { // N = 1, S = 0: chi co so 0
cout << 0 << "\n";
return;
}
string res;
long long R = S;
for (long long i = 0; i < N; i++) {
int d = min<long long>(9, R); // chu so lon nhat co the dat o vi tri nay
res += char('0' + d);
R -= d;
}
cout << res << "\n";
}
int main() {
freopen("MATKHAU.INP", "r", stdin);
freopen("MATKHAU.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long N, S;
cin >> N >> S;
sub1(N, S);
return 0;
}
Bình luận