Hướng dẫn giải của Đếm số chẵn lẻ (đề KS ĐH 2024)
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
Số ~X~ thỏa mãn khi các vị trí lẻ (đếm từ trái, bắt đầu từ 1) chứa chữ số lẻ và các vị trí chẵn chứa chữ số chẵn. Cần đếm số như vậy trong đoạn ~[1; R]~.
Sub 1: Duyệt từng số — ~O(R \cdot \log R)~, dùng khi ~R \le 10^6~
Duyệt mọi số từ ~1~ đến ~R~ và kiểm tra từng chữ số theo quy tắc chẵn lẻ. Nếu chỉ nộp sub này: đúng 9/20 test.
Sub 2: Đếm theo công thức — ~O(\log R)~
Mỗi vị trí có đúng 5 chữ số hợp lệ, nên số có ~d~ chữ số hợp lệ có ~5^d~ số. Với các số cùng độ dài với ~R~, duyệt từng chữ số của ~R~ để cộng số lượng các số nhỏ hơn ~R~, rồi kiểm tra chính ~R~. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Nếu ~R \le 10^6~ dùng sub 1, còn lại dùng sub 2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
long long R; // gioi han tren cua doan [1; R]
// Kiem tra mot so co phai "so chan le" khong: vi tri le (tu trai, bat dau tu 1) la chu so le,
// vi tri chan la chu so chan
bool good(long long x) {
string s = to_string(x);
for (int i = 0; i < (int)s.size(); i++) {
int pos = i + 1;
int d = s[i] - '0';
if (pos % 2 == 1 && d % 2 == 0) return false;
if (pos % 2 == 0 && d % 2 == 1) return false;
}
return true;
}
// Sub 1: duyet tung so tu 1 den R roi kiem tra — dung khi R <= 10^6
void sub1() {
long long cnt = 0;
for (long long x = 1; x <= R; x++) if (good(x)) cnt++;
cout << cnt << "\n";
}
// Sub 2: cong thuc. Moi vi tri co 5 chu so hop le nen so co d chu so hop le co 5^d so.
// Voi so co dung D chu so, duyet tung chu so cua R va dem cac so nho hon R
void sub2() {
string s = to_string(R);
int D = s.size();
long long pw[20];
pw[0] = 1;
for (int i = 1; i < 20; i++) pw[i] = pw[i - 1] * 5;
long long cnt = 0;
for (int d = 1; d < D; d++) cnt += pw[d]; // cac so co it chu so hon R
bool ok = true;
for (int i = 0; i < D && ok; i++) {
int pos = i + 1;
int r = s[i] - '0';
for (int c = 0; c < r; c++) { // chon chu so nho hon R tai vi tri pos
bool validc = (pos % 2 == 1) ? (c % 2 == 1) : (c % 2 == 0);
if (validc) cnt += pw[D - pos];
}
bool validr = (pos % 2 == 1) ? (r % 2 == 1) : (r % 2 == 0);
if (!validr) ok = false; // R di lech khuon mau, dung
}
if (ok) cnt++; // chinh R
cout << cnt << "\n";
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> R;
if (R <= 1000000) sub1();
else sub2();
return 0;
}
Bình luận