Hướng dẫn giải của [200 đề thầy Đức] Bài 138: Số đẹp
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
Cho số $x$ có $n$ chữ số và số $k < n$. Số $y$ được gọi là đẹp nếu $b[i] = b[i+k]$ với mọi $i$, tức là chữ số ở vị trí $i$ và $i+k$ luôn giống nhau. Cần tìm số $y$ đẹp nhỏ nhất không nhỏ hơn $x$.
Nhận xét: một số đẹp được quyết định hoàn toàn bởi $k$ chữ số đầu tiên. Lặp lại tiền tố này cho đủ độ dài là ra số đẹp.
- Nếu số có $n$ chữ số được xây từ tiền tố của $x$ đã lớn hơn hoặc bằng $x$, thì đó là đáp án.
- Nếu không, phải tăng tiền tố lên một đơn vị. Nếu tiền tố toàn chữ $9$ thì không tăng được, khi đó đáp án có $n+1$ chữ số và là số $1$ theo sau bởi $k-1$ chữ số $0$, lặp lại đến đủ $n+1$ chữ số.
Sub 1: Vét cạn theo tiền tố — ~O(10^k \cdot n)~, dùng khi ~n \le 1000~ và ~k \le 2~
Thử lần lượt mọi tiền tố $k$ chữ số từ tiền tố của $x$ trở đi. Với mỗi tiền tố, xây số có $n$ chữ số và so sánh với $x$, lấy số đầu tiên không nhỏ hơn $x$. Nếu không có thì dùng đáp án $n+1$ chữ số.
Kết quả chấm riêng sub này: đúng 6/22 test, các test còn lại nằm ngoài miền của sub (lỗi chạy vì $k$ lớn làm $10^k$ vượt kiểu số nguyên).
Sub 2: Tham lam theo tiền tố — ~O(n)~
Lấy $k$ chữ số đầu của $x$, lặp lại để có $y$. Nếu $y \ge x$ thì in $y$. Nếu $y < x$ thì cộng 1 vào tiền tố (có nhớ), và xây lại $y$. Nếu cộng 1 làm tràn (tiền tố toàn $9$) thì đáp án có $n+1$ chữ số.
Bẫy cần chú ý: tiền tố tăng lên 1 vẫn có chữ số đầu khác $0$ vì $x$ có chữ số đầu khác $0$. Khi tiền tố toàn $9$ thì phải chuyển sang trường hợp $n+1$ chữ số, không được in tiền tố $0\ldots0$.
Kết quả chấm riêng sub này: đúng 22/22 test.
Chương trình hoàn chỉnh
Chương trình đọc $n$, $k$ và $x$. Nếu $n \le 1000$ và $k \le 2$ thì gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub1 vẫn ăn điểm các test nhỏ nếu sub2 chưa làm kịp.
#include <bits/stdc++.h>
using namespace std;
int n, k;
string x; // số x có n chữ số
// Lặp chuỗi p (độ dài k) cho đủ len chữ số: y[i] = p[i mod k], tức b[i] = b[i+k]
string repeatPrefix(const string& p, int len) {
string y(len, '0');
for (int i = 0; i < len; i++) y[i] = p[i % k];
return y;
}
// Đáp án khi không có số đẹp có n chữ số >= x: số n+1 chữ số nhỏ nhất đẹp là "1" + (k-1) số 0 lặp lại
void printLonger() {
string p = "1" + string(k - 1, '0');
string y = repeatPrefix(p, n + 1);
cout << n + 1 << "\n" << y << "\n";
}
// Sub 1: vét cạn — thử lần lượt mọi tiền tố k chữ số, từ tiền tố của x trở đi;
// với mỗi tiền tố xây y có n chữ số và so sánh với x, lấy y >= x đầu tiên.
// Dùng khi n <= 1000 và k <= 2 (không quá 100 tiền tố)
void sub1() {
int P = stoi(x.substr(0, k));
int lim = 1;
for (int i = 0; i < k; i++) lim *= 10; // số tiền tố k chữ số: 0..lim-1
for (int v = P; v < lim; v++) {
string p = to_string(v);
p = string(k - p.size(), '0') + p;
string y = repeatPrefix(p, n);
if (y >= x) { cout << n << "\n" << y << "\n"; return; }
}
printLonger();
}
// Sub 2: tham lam — lấy tiền tố k chữ số của x, lặp để có y. Nếu y < x thì tăng tiền tố lên 1
// (nếu tiền tố toàn chữ 9 thì không tăng được nữa: đáp án có n+1 chữ số). Dùng cho mọi n
void sub2() {
string p = x.substr(0, k);
string y = repeatPrefix(p, n);
if (y < x) {
// Tăng tiền tố lên 1 đơn vị
int i = k - 1;
while (i >= 0 && p[i] == '9') { p[i] = '0'; i--; }
if (i < 0) { printLonger(); return; }
p[i]++;
y = repeatPrefix(p, n);
}
cout << n << "\n" << y << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k >> x;
if (n <= 1000 && k <= 2) sub1(); // n nhỏ và k nhỏ: vét cạn cho chắc
else sub2(); // dữ liệu lớn: tham lam theo tiền tố
return 0;
}
Bình luận