Hướng dẫn giải của Số đẹp 1
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
, , ,
Editorial for ptit007: Số đẹp 1
Hiểu bài toán
Cho một số nguyên dương N (1 ≤ N ≤ 10000), tìm số đẹp nhỏ nhất sao cho số đó ≥ N. Số đẹp được định nghĩa là số có thể biểu diễn dưới dạng tổng các số lũy thừa của 3 khác nhau. Ví dụ: 4 = 3^1 + 3^0 (hợp lệ), nhưng 6 = 3^1 + 3^1 (không hợp lệ vì trùng lũy thừa).
Các cách tiếp cận
Cách Tăng dần N (Naive Search)
#include <iostream>
using namespace std;
bool isBeautiful(int n) {
int count[20] = {0}; // Đếm số lần xuất hiện của mỗi lũy thừa 3
int idx = 0;
while (n > 0) {
int digit = n % 3;
if (digit != 0 && count[idx] > 0) return false; // Đã có lũy thừa này rồi
if (digit > 1) return false; // Lớn hơn 1 thì không thể chỉ dùng 1 lần
count[idx] = digit;
n /= 3;
idx++;
}
return true;
}
int main() {
int t; cin >> t;
while(t--) {
int n; cin >> n;
while(true) {
if (isBeautiful(n)) {
cout << n << endl;
break;
}
n++;
}
}
return 0;
}
- Time Complexity: O(T * N * log N)
- Space Complexity: O(1)
Phương pháp này bắt đầu từ N và kiểm tra từng số xem có phải là số đẹp hay không bằng cách chuyển đổi sang hệ cơ số 3. Nếu tìm thấy số 2 trong biểu diễn hệ cơ số 3, số đó không đẹp vì yêu cầu các lũy thừa phải khác nhau (tức chỉ được dùng 0 hoặc 1 lần). Cách này đơn giản nhưng có thể chậm nếu khoảng cách từ N đến số đẹp tiếp theo quá lớn.
Cách Quay lui (Backtracking)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, res;
vector<int> powers;
void backtrack(int idx, int sum) {
if (sum >= n) {
res = min(res, sum);
return;
}
if (idx == powers.size()) return;
// Bỏ qua powers[idx]
backtrack(idx + 1, sum);
// Chọn powers[idx]
if (sum + powers[idx] <= res) { // Pruning
backtrack(idx + 1, sum + powers[idx]);
}
}
int main() {
// Tạo trước các lũy thừa của 3 (3^0 -> 3^15)
int tmp = 1;
while (tmp <= 100000) {
powers.push_back(tmp);
tmp *= 3;
}
int t; cin >> t;
while(t--) {
cin >> n;
res = 1e9;
backtrack(0, 0);
cout << res << "\n";
}
return 0;
}
- Time Complexity: O(2^K) với K là số lượng lũy thừa 3 nhỏ hơn bound (khoảng 2^16)
- Space Complexity: O(K)
Sử dụng kỹ thuật quay lui để tạo tất cả các tổng hợp lệch từ các lũy thừa của 3. Mỗi lũy thừa có thể được chọn hoặc không chọn. Ta lưu lại tổng nhỏ nhất ≥ N. Cách này sinh ra tất cả các tổ hợp có thể, số lượng tổ hợp là 2^16 ≈ 65000, đủ nhanh cho N nhỏ.
Cách Xử lý theo hệ cơ số 3 (Greedy/DP)
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while(T--) {
int N;
cin >> N;
while(true) {
int temp = N;
bool valid = true;
while(temp > 0) {
if (temp % 3 == 2) {
valid = false;
break;
}
temp /= 3;
}
if (valid) {
cout << N << '\n';
break;
}
N++;
}
}
return 0;
}
- Time Complexity: O(T * D * log N)
- Space Complexity: O(1)
Đây là cách hiệu quả nhất trong các giải pháp đã cho. Số đẹp tương đương với các số mà khi viết dưới dạng hệ cơ số 3 chỉ chứa các chữ số 0 và 1 (không chứa 2). Nếu N không thỏa mãn, ta chỉ cần tăng N lên 1 và kiểm tra lại cho đến khi tìm thấy số thỏa mãn. Do mật độ số đẹp khá dày đặc (tương đương số có dạng 0/1 trong hệ cơ số 3), số lần lặp sẽ rất nhỏ.
Cách Dynamic Programming (Sinh số)
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> p;
for (int i = 1; i <= 100000; i *= 3)
p.push_back(i);
vector<bool> dp(10001, false);
dp[0] = true;
// Sinh ra tất cả các tổng hợp lệch
for (int x : p) {
for (int j = 10000; j >= x; j--) {
if (dp[j - x]) dp[j] = true;
}
}
// Precompute kết quả
vector<int> ans(10001);
int last = 0;
for (int i = 1; i <= 10000; i++) {
if (dp[i]) last = i;
ans[i] = last;
}
int t; cin >> t;
while(t--) {
int n; cin >> n;
cout << ans[n] << "\n";
}
return 0;
}
- Time Complexity: O(10000 * log 10000) precompute, O(1) per query
- Space Complexity: O(10000)
Sử dụng quy hoạch động (Knapsack) để sinh ra tất cả các tổng có thể tạo được từ các lũy thừa của 3 nhỏ hơn 10000. Sau đó, với mỗi N, ta chỉ cần tìm số đẹp lớn nhất ≤ N. Đây là cách tối ưu hóa cho các bài toán có giới hạn N nhỏ nhưng số lượng test case lớn.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(T * N * log N) | O(1) | Tăng dần N (Naive Search) |
| 2 | O(2^K) với K là số lượng lũy thừa 3 nhỏ hơn bound (khoảng 2^16) | O(K) | Quay lui (Backtracking) |
| 3 | O(T * D * log N) | O(1) | Xử lý theo hệ cơ số 3 (Greedy/DP) |
| 4 | O(10000 * log 10000) precompute, O(1) per query | O(10000) | Dynamic Programming (Sinh số) |
Bài học kinh nghiệm
- Số đẹp tương đương với các số có biểu diễn hệ cơ số 3 không chứa chữ số 2.
- Vì N ≤ 10000, ta có thể tối ưu hóa bằng cách precompute trước các số đẹp hoặc sinh ra các tổ hợp lũy thừa.
- Khoảng cách giữa các số đẹp khá nhỏ, nên việc duyệt tăng dần (N++) thường rất nhanh.
Lỗi thường gặp
- Lầm tưởng rằng số đẹp là số có tổng các chữ số trong hệ cơ số 3 bằng 1, thực ra là không chứa số 2.
- Quên rằng N có thể bằng chính số đẹp đó, không cần tìm số lớn hơn.
- Sử dụng mảng quá nhỏ khi tính lũy thừa 3 (3^15 > 10000).
Bình luận