Hướng dẫn giải của [200 đề thầy Đức] Bài 13: Tìm số thứ N
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
Dãy các số chỉ gồm chữ số 4 và 7, sắp tăng dần: 4, 7, 44, 47, 74, 77, \dots. Tìm số thứ ~N~ trong dãy.
Sub 1: Sinh danh sách và tra — ~O(\text{hằng số})~ mỗi truy vấn sau khi sinh, dùng khi ~N \le 1000~
Sinh các số gồm chữ số 4 và 7 theo BFS: bắt đầu từ 4, 7, sau mỗi số thêm 4 rồi thêm 7. Thứ tự sinh chính là thứ tự tăng dần. Lấy phần tử thứ ~N~ trong danh sách đã sinh (danh sách đủ hơn 1000 số).
Nếu chỉ nộp sub này: đúng 21/21 test.
Sub 2: Công thức theo bit — ~O(\log N)~, dùng khi mọi trường hợp còn lại
Có một tương ứng giữa số thứ ~N~ và biểu diễn nhị phân của ~N+1~. Bỏ bit cao nhất, bit 0 ứng với chữ số 4, bit 1 ứng với chữ số 7. Ví dụ ~N = 5~: ~6 = 110_2~, bỏ bit đầu được ~10_2~, cho 74.
Nếu chỉ nộp sub này: đúng 21/21 test.
Chương trình hoàn chỉnh
Chương trình đọc ~T~ rồi từng ~N~. Nếu ~N \le 1000~ thì gọi sub1, ngược lại gọi sub2. Ví dụ: ~N = 11~ cho 744.
#include <bits/stdc++.h>
using namespace std;
long long N;
// Sub 1: vet can. Sinh cac so chi gom chu so 4 va 7 theo BFS (do dai tang dan, cung do dai thi theo thu tu 4 < 7),
// day chinh la thu tu tang dan. Lay phan tu thu N. Dung khi N <= 1000.
void sub1() {
static vector<string> lst;
if (lst.empty()) {
lst = {"4", "7"};
for (size_t i = 0; lst.size() < 2100; i++) {
string a = lst[i] + "4";
string b = lst[i] + "7";
lst.push_back(a);
lst.push_back(b);
}
}
cout << lst[N - 1] << "\n";
}
// Sub 2: cong thuc theo bit. Dat m = N + 1 va bo bit cao nhat cua m.
// Moi bit con lai: 0 ung voi chu so 4, 1 ung voi chu so 7. O(log N).
void sub2() {
unsigned long long m = (unsigned long long)N + 1;
int h = 63;
while (!((m >> h) & 1)) h--;
string s;
for (int i = h - 1; i >= 0; i--) s += ((m >> i) & 1) ? '7' : '4';
cout << s << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
cin >> N;
if (N <= 1000) sub1();
else sub2();
}
return 0;
}
Bình luận