Hướng dẫn giải của F08: Số chẵn lẻ 2
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 các số nguyên dương trong đoạn ~[1, N]~ mà chữ số ở vị trí lẻ (tính từ trái) là số lẻ, chữ số ở vị trí chẵn là số chẵn. Với ~N \le 10^9~.
Sub 1: Thử từng số — ~O(N \log N)~, dùng khi ~N \le 10^6~
Với mỗi số từ 1 đến ~N~, đổi sang xâu chữ số rồi kiểm tra từng chữ số theo vị trí. Cách này đủ nhanh khi ~N~ nhỏ.
Nếu chỉ nộp sub này: đúng 9/20 test.
Sub 2: Đếm bằng công thức — ~O(\log N)~, dùng khi mọi trường hợp còn lại
Mỗi vị trí có đúng 5 chữ số hợp lệ (5 chữ số lẻ hoặc 5 chữ số chẵn, vị trí đầu không được là 0). Vì vậy số các số có ~L~ chữ số thỏa điều kiện là ~5^L~. Với các số có ít chữ số hơn ~N~, cộng ~5^L~ là xong. Với các số cùng độ dài ~N~, duyệt từng chữ số của ~N~: tại mỗi vị trí, thử các chữ số nhỏ hơn có đúng tính chẵn lẻ, mỗi lựa chọn đếm ~5^{\text{số vị trí còn lại}}~ số, rồi tiếp tục nếu chữ số của ~N~ cũng hợp lệ.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Đề chỉ có một ràng buộc ~N \le 10^9~. Sub 1 là vét cạn, sub 2 là đếm theo chữ số.
Chương trình đọc ~N~. Nếu ~N \le 10^6~ thì gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
long long N;
// Kiem tra mot so: chu so o vi tri le (1,3,5...) phai le, o vi tri chan (2,4,...) phai chan
bool dungQuyDinh(long long x) {
string s = to_string(x);
for (size_t i = 0; i < s.size(); i++) {
int d = s[i] - '0';
bool viTriLe = (i % 2 == 0); // i tinh tu 0 -> vi tri thu i+1 la le khi i chan
if (viTriLe && d % 2 == 0) return false;
if (!viTriLe && d % 2 == 1) return false;
}
return true;
}
// Sub 1: vet can, thu tung so tu 1 den N. Dung khi N <= 10^6
void sub1() {
long long cnt = 0;
for (long long x = 1; x <= N; x++)
if (dungQuyDinh(x)) cnt++;
cout << cnt << "\n";
}
// Luy thua 5^e
long long pw5(int e) {
long long r = 1;
for (int i = 0; i < e; i++) r *= 5;
return r;
}
// Sub 2: dem bang cong thuc. Moi vi tri co dung 5 chu so hop le (5 le hoac 5 chan),
// nen so cac so co L chu so dung quy dinh la 5^L. Voi so cung do dai N thi duyet tung chu so.
void sub2() {
string s = to_string(N);
int m = s.size();
long long ans = 0;
for (int L = 1; L < m; L++) ans += pw5(L); // cac so co it chu so hon N
bool khop = true; // prefix cua N con dung quy dinh?
for (int i = 0; i < m && khop; i++) {
bool canLe = (i % 2 == 0);
int cur = s[i] - '0';
int conLai = m - 1 - i; // so vi tri con lai sau i
// chon chu so d < cur o vi tri i, cac vi tri sau tu do
for (int d = (i == 0 ? 1 : 0); d < cur; d++)
if ((d % 2 == 1) == canLe) ans += pw5(conLai);
if ((cur % 2 == 1) != canLe) khop = false;
}
if (khop) ans++; // chinh N
cout << ans << "\n";
}
int main() {
cin >> N;
if (N <= 1000000) sub1();
else sub2();
return 0;
}
Bình luận