Hướng dẫn giải của Nỗi ám ảnh của Iroha
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.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Hiểu bài toán
Iroha cần thanh toán N yên nhưng cô ấy không thích sử dụng một số chữ số nhất định (có K chữ số bị cấm). Cô ấy muốn đưa cho thu ngân một số tiền X sao cho X >= N và tất cả các chữ số trong X đều không nằm trong danh sách cấm. Tìm X nhỏ nhất thỏa mãn.
Các cách tiếp cận
Cách Brute Force (Tìm kiếm tuần tự)
#include <bits/stdc++.h>
using namespace std;
bool ok(int x, const vector<bool>& bad) {
if (x == 0) {
return !bad[0];
}
while (x > 0) {
int d = x % 10;
if (bad[d]) return false;
x /= 10;
}
return true;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, K;
cin >> N >> K;
vector<bool> bad(10, false);
for (int i = 0; i < K; i++) {
int d;
cin >> d;
bad[d] = true;
}
int x = N;
while (true) {
if (ok(x, bad)) {
cout << x;
return 0;
}
x++;
}
return 0;
}
- Time Complexity: O(X) (X là kết quả đầu ra)
- Space Complexity: O(1)
Đây là cách tiếp cận trực quan nhất. Bắt đầu từ số tiền N, kiểm tra xem nó có chứa chữ số cấm không. Nếu có, tăng dần số tiền lên 1 đơn vị cho đến khi tìm được số tiền thỏa mãn. Với ràng buộc N < 10000, số lần lặp sẽ không quá lớn nên phương pháp này hoàn toàn chấp nhận được.
Cách BFS / Quay lui (Tạo số từ các chữ số cho phép)
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int main() {
int N, K;
cin >> N >> K;
vector<bool> bad(10, false);
for (int i = 0; i < K; i++) {
int d;
cin >> d;
bad[d] = true;
}
vector<int> allowed;
for (int i = 0; i <= 9; i++) {
if (!bad[i]) allowed.push_back(i);
}
queue<int> q;
// Khởi tạo các số có 1 chữ số (không bao gồm 0 nếu N > 0)
for (int d : allowed) {
if (d == 0 && N > 0) continue; // Tránh số 0 leading
q.push(d);
if (d >= N) {
cout << d << endl;
return 0;
}
}
while (!q.empty()) {
int curr = q.front();
q.pop();
for (int d : allowed) {
long long next_val = (long long)curr * 10 + d;
// Nếu số quá lớn (nằm ngoài phạm vi cần thiết), có thể bỏ qua
// Tuy nhiên, do N nhỏ, ta có thể kiểm tra trực tiếp
if (next_val >= N) {
cout << next_val << endl;
return 0;
}
// Chỉ thêm vào queue nếu số chưa vượt quá N quá nhiều
// Hoặc giới hạn độ dài số
if (next_val < 100000) q.push(next_val);
}
}
return 0;
}
- Time Complexity: O(M) (M là số lượng số được tạo ra)
- Space Complexity: O(M)
Tạo các số hợp lệ bằng cách kết hợp các chữ số cho phép. Sử dụng BFS để duyệt theo độ dài tăng dần (1 chữ số, 2 chữ số...). Số đầu tiên tìm thấy >= N là đáp án. Cách này sinh ra các số theo thứ tự tăng dần, đảm bảo tìm được số nhỏ nhất.
Cách Tối ưu hóa Biên (Greedy)
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main() {
int N, K;
cin >> N >> K;
vector<bool> bad(10, false);
for (int i = 0; i < K; i++) {
int d;
cin >> d;
bad[d] = true;
}
vector<int> allowed;
for (int i = 0; i <= 9; i++) {
if (!bad[i]) allowed.push_back(i);
}
string s = to_string(N);
int len = s.length();
int min_allowed = allowed[0];
int first_allowed = -1;
for (int d : allowed) {
if (d > 0) { first_allowed = d; break; }
}
// Nếu không có số khác 0, phải dùng 0 (trường hợp N=0) hoặc thêm chữ số
if (first_allowed == -1) first_allowed = 0;
// Thử tìm số có cùng độ dài
string res = "";
int i;
for (i = 0; i < len; i++) {
int digit = s[i] - '0';
// Kiểm tra các số >= digit trong allowed
bool found = false;
for (int d : allowed) {
if (d >= digit) {
// Nếu d == digit, tiếp tục kiểm tra phần sau
if (d == digit) {
res += to_string(d);
found = true;
break;
} else {
// Nếu d > digit, ta chỉ cần điền phần còn lại bằng số nhỏ nhất
res += to_string(d);
for (int j = i + 1; j < len; j++) {
res += to_string(min_allowed);
}
cout << res << endl;
return 0;
}
}
}
if (!found) {
// Không tìm thấy số >= digit tại vị trí i
// Cần quay lui về vị trí trước đó
int j = i - 1;
while (j >= 0) {
// Tìm số lớn hơn số tại j
int cur_dig = s[j] - '0';
bool increased = false;
for (int d : allowed) {
if (d > cur_dig) {
res[j] = '0' + d;
// Điền phần còn lại bằng số nhỏ nhất
for (int k = j + 1; k < len; k++) {
res[k] = '0' + min_allowed;
}
cout << res << endl;
return 0;
}
}
// Nếu không tìm thấy, tiếp tục lui
// (Trường hợp này hiếm ở N nhỏ, nhưng để an toàn)
if (j == 0 && cur_dig == 0) break; // Không thể lui thêm
j--;
}
// Nếu không thể tìm số cùng độ dài, phải tạo số có độ dài lớn hơn
break;
}
}
// Nếu đến đây mà chưa return, nghĩa là không tìm được số cùng độ dài
// Tạo số có độ dài len + 1
if (first_allowed == 0 && len == 1) {
// Trường hợp đặc biệt N=0 nhưng 0 bị cấm -> không thể xảy ra theo đề bài
}
if (first_allowed == 0) first_allowed = allowed[1]; // Bỏ qua 0 nếu là số đầu tiên
string ans = "";
ans += to_string(first_allowed);
for (int i = 0; i < len; i++) ans += to_string(min_allowed);
cout << ans << endl;
return 0;
}
- Time Complexity: O(L * 10) (L là số chữ số của N)
- Space Complexity: O(L)
Đây là thuật toán tối ưu nhất, chạy theo O(Số chữ số). Nó phân tích N từ trái sang phải. Tại mỗi vị trí, cố gắng giữ nguyên chữ số của N nếu có thể. Nếu không thể (vì chữ số đó bị cấm), ta thử thay bằng chữ số lớn hơn tiếp theo trong danh sách cho phép và điền phần còn lại bằng số nhỏ nhất. Nếu không có chữ số lớn hơn tại vị trí đó, ta phải quay lui về vị trí trước đó và tăng nó lên. Nếu không thể tạo số cùng độ dài, ta tạo số có độ dài lớn hơn (bắt đầu bằng chữ số khác 0 nhỏ nhất, rồi điền hết bằng số nhỏ nhất).
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(X) (X là kết quả đầu ra) | O(1) | Brute Force (Tìm kiếm tuần tự) |
| 2 | O(M) (M là số lượng số được tạo ra) | O(M) | BFS / Quay lui (Tạo số từ các chữ số cho phép) |
| 3 | O(L * 10) (L là số chữ số của N) | O(L) | Tối ưu hóa Biên (Greedy) |
Bài học kinh nghiệm
- Vì N < 10000, số tiền cần tìm không vượt quá 100000 quá nhiều, nên phương pháp Brute Force chạy từ N trở lên là hoàn toàn khả thi và dễ implement nhất.
- Các chữ số cho phép có thể được lưu vào một mảng boolean hoặc vector để kiểm tra O(1).
- Phương pháp sinh số (BFS) hoặc phân tích số (Greedy) cho độ phức tạp tốt hơn về mặt lý thuyết nhưng code phức tạp hơn.
Lỗi thường gặp
- Xử lý trường hợp số 0: Số 0 có thể là số cho phép, nhưng không thể là số đứng đầu (leading zero) của một số có nhiều chữ số.
- Sai lệch logic khi quay lui: Trong phương pháp tối ưu, nếu không tìm được số thỏa mãn tại một vị trí, cần phải lùi về sau để tăng số trước đó, đảm bảo số tìm được nhỏ hơn số có độ dài dài hơn.
Bình luận