Hướng dẫn giải của LUCKY LẠI MAY MẮN
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
Bài toán yêu cầu tìm số may mắn (lucky number) nhỏ nhất chia hết cho N. Số may mắn được định nghĩa là số chỉ bao gồm các chữ số 6 và 8. Nếu không tồn tại số như vậy (hoặc số quá dài, ví dụ > 200 chữ số), in ra -1.
Các cách tiếp cận
Cách Quay lui (Backtracking) - Duyệt tất cả chuỗi
void solve() {
int n;
cin >> n;
queue<string> q;
q.push("6");
q.push("8");
while (!q.empty()) {
string s = q.front(); q.pop();
if (s.length() > 200) continue; // Giới hạn độ dài
// Tính số dư của s chia cho n
long long rem = 0;
for (char c : s) rem = (rem * 10 + (c - '0')) % n;
if (rem == 0) {
cout << s << endl;
return;
}
q.push(s + "6");
q.push(s + "8");
}
cout << -1 << endl;
}
- Time Complexity: O(2^L) hoặc O(N) tùy vào cách tối ưu, nhưng trong thực tế do giới hạn độ dài nên số lượng trạng thái là 2^200 (quá lớn nếu không có tối ưu). Tuy nhiên, nếu dùng BFS trên graph các số dư, độ phức tạp là O(N).
- Space Complexity: O(N) hoặc O(2^L)
Phương pháp này sinh ra các số may mắn theo thứ tự tăng dần độ dài (BFS). Nó kiểm tra từng số xem có chia hết cho N không. Nếu tìm thấy số dư 0, ta in ra số đó. Nếu độ dài vượt quá giới hạn (ví dụ 200), dừng lại và in -1. Tuy nhiên, sinh ra tất cả chuỗi là không khả thi nếu độ dài lớn.
Cách BFS trên Graph các số dư (BFS on Remainders)
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> parent(n, -1);
vector<char> digit(n, 0);
vector<bool> visited(n, false);
queue<int> q;
// Bắt đầu với 6 và 8
int r6 = 6 % n;
int r8 = 8 % n;
if (r6 == 0) { cout << "6" << endl; return 0; }
if (r8 == 0) { cout << "8" << endl; return 0; }
q.push(r6);
visited[r6] = true;
parent[r6] = -1; // Root
digit[r6] = '6';
if (!visited[r8]) {
q.push(r8);
visited[r8] = true;
parent[r8] = -1;
digit[r8] = '8';
}
int found_rem = -1;
while (!q.empty()) {
int r = q.front(); q.pop();
// Thêm 6
int next6 = (r * 10 + 6) % n;
if (!visited[next6]) {
visited[next6] = true;
parent[next6] = r;
digit[next6] = '6';
if (next6 == 0) { found_rem = next6; break; }
q.push(next6);
}
// Thêm 8
int next8 = (r * 10 + 8) % n;
if (!visited[next8]) {
visited[next8] = true;
parent[next8] = r;
digit[next8] = '8';
if (next8 == 0) { found_rem = next8; break; }
q.push(next8);
}
}
if (found_rem == -1) {
cout << -1 << endl;
} else {
string res = "";
int curr = 0;
while (curr != -1) {
res += digit[curr];
curr = parent[curr];
}
reverse(res.begin(), res.end());
cout << res << endl;
}
return 0;
}
- Time Complexity: O(N)
- Space Complexity: O(N)
Đây là cách tối ưu nhất. Ta xét các số dư từ 0 đến N-1. Mỗi số dư là một node trong graph. Từ node u, ta có thể đi tới node (u10 + 6) % N và (u10 + 8) % N. Ta dùng BFS để tìm đường đi ngắn nhất từ các node bắt đầu (6%N, 8%N) đến node 0. Khi đến node 0, ta truy xuất đường đi để in ra số. Độ phức tạp là O(N) vì có tối đa N số dư.
Cách Tạo chuỗi theo sớ lượng số 6 và 8 (Duyệt số lượng)
#include <iostream>
#include <string>
#include <vector>
using namespace std;
long long modBig(string s, int n) {
long long res = 0;
for (char c : s) {
res = (res * 10 + (c - '0')) % n;
}
return res;
}
int main() {
int k;
cin >> k;
// Duyệt tổng số chữ số (len)
for (int len = 1; len <= 200; len++) {
// Duyệt số lượng số 8 (d8) từ 0 đến len
for (int d8 = 0; d8 <= len; d8++) {
int d6 = len - d8;
// Tạo chuỗi: d8 số 8 ở đầu, d6 số 6 ở cuối
string s = "";
for (int i = 0; i < d8; i++) s += '8';
for (int i = 0; i < d6; i++) s += '6';
if (modBig(s, k) == 0) {
cout << s << endl;
return 0;
}
}
}
cout << -1 << endl;
return 0;
}
- Time Complexity: O(L^2 * N) hoặc O(L^2) (tùy cách tính N), nhưng thực tế L nhỏ (<= 200)
- Space Complexity: O(L)
Giả sử số may mắn có dạng một chuỗi gồm các số 8 ở đầu và các số 6 ở sau (ví dụ: 888666). Ta chỉ cần duyệt tổng độ dài chuỗi, và với mỗi độ dài, duyệt số lượng số 8. Đây là cách tiếp cận tham lam hoặc thử các cấu trúc chuỗi đơn giản. Tuy nhiên, số may mắn không nhất thiết phải có dạng 8...86...6. Ví dụ: 6868. Do đó, cách này chỉ đúng nếu có giả định về cấu trúc số (thường dùng trong các bài toán quy hoạch động hoặc BFS đơn giản). Trong Solution 2, tác giả dùng cách này và may mắn nó pass (có thể do test yếu hoặc giả định đúng trong phạm vi bài toán này). Solution 1 dùng BFS chuỗi thuần túy, tối ưu bằng map để lưu số dư.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(2^L) hoặc O(N) tùy vào cách tối ưu, nhưng trong thực tế do giới hạn độ dài nên số lượng trạng thái là 2^200 (quá lớn nếu không có tối ưu). Tuy nhiên, nếu dùng BFS trên graph các số dư, độ phức tạp là O(N). | O(N) hoặc O(2^L) | Quay lui (Backtracking) - Duyệt tất cả chuỗi |
| 2 | O(N) | O(N) | BFS trên Graph các số dư (BFS on Remainders) |
| 3 | O(L^2 * N) hoặc O(L^2) (tùy cách tính N), nhưng thực tế L nhỏ (<= 200) | O(L) | Tạo chuỗi theo sớ lượng số 6 và 8 (Duyệt số lượng) |
Bài học kinh nghiệm
- Bài toán có thể mô hình hóa thành tìm đường đi ngắn nhất trên graph các số dư (mod N).
- Chỉ cần quan tâm đến số dư khi chia cho N, không cần quan tâm đến giá trị thực của số (tránh tràn số).
- Nếu dùng BFS chuỗi thuần túy, cần giới hạn độ dài chuỗi để tránh TLE/MLE.
Lỗi thường gặp
- Sử dụng kiểu số nguyên (int/long long) để lưu số may mắn直接可能导致 tràn số (overflow) vì số có thể rất dài.
- Bỏ qua trường hợp số 6 hoặc 8 chia hết cho N ngay từ đầu.
- Quên kiểm tra điều kiện dừng (tìm thấy số 0) trong vòng lặp BFS.
Bình luận