Hướng dẫn giải của LOOP28: Đếm số đẹp
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
Đếm số đẹp không vượt quá N, với N ≤ 10^5. Cách đơn giản nhất là kiểm tra từng số; cách tốt hơn là chỉ sinh các số đẹp bằng cách ghép thêm chữ số 6 hoặc 8.
Sub 1: Vét cạn — ~O(N log N)~
Với mỗi số i từ 1 đến N, kiểm tra các chữ số của i có thuộc {6, 8} hay không và đếm. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
// Kiểm tra số x có chỉ chứa chữ số 6 hoặc 8 hay không
bool beautiful(long long x) {
while (x > 0) {
int d = x % 10;
if (d != 6 && d != 8) return false;
x /= 10;
}
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n;
cin >> n;
// Vét cạn: thử từng số từ 1 đến N
int cnt = 0;
for (long long i = 1; i <= n; i++)
if (beautiful(i)) cnt++;
cout << cnt << "\n";
return 0;
}
Sub 2: Sinh số đẹp bằng đệ quy — ~O(số lượng số đẹp)~
Bắt đầu từ 6 và 8, mỗi số x sinh ra hai số x·10+6 và x·10+8. Nếu x > N thì dừng, vì các số sinh tiếp theo đều lớn hơn N. Mỗi số đẹp được sinh đúng một lần nên cnt là đáp án. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
long long N;
int cnt = 0;
// Sinh các số đẹp bằng cách thêm chữ số 6 hoặc 8 vào cuối.
// Mỗi số sinh ra đều đẹp, và mọi số đẹp đều được sinh đúng một lần.
void gen(long long x) {
if (x > N) return; // vượt quá N thì mọi số sinh tiếp theo cũng lớn hơn N
cnt++;
gen(x * 10 + 6);
gen(x * 10 + 8);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N;
gen(6);
gen(8);
cout << cnt << "\n";
return 0;
}
Bình luận