Hướng dẫn giải của Tìm số (đề HSG 9 Phú Thọ 2014-2015)
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
Cho số tự nhiên a, dãy a1 = a, ai = a{i-1} a{i-1} (viết liền). Cần tìm chữ số thứ k (từ trái sang) của a_n. Đề dùng file TIMSO.INP và TIMSO.OUT, với a, n, k <= 10^9.
Sub 1: Chỉ giữ k chữ số đầu — ~O(k \log k)~, dùng khi ~k \le 255~
Vì ai = a{i-1} a{i-1} nên k chữ số đầu của ai chỉ phụ thuộc vào k chữ số đầu của a{i-1}. Ta lặp, mỗi lần ghép đôi chuỗi rồi cắt còn k ký tự, cho đến khi đủ k ký tự. Đây là vét cạn trên tiền tố, không cần dựng cả an.
Nếu chỉ nộp sub này: đúng 10/28 test (các test k lớn bị quá giờ).
Sub 2: Lần ngược vị trí — ~O(\log k)~
Độ dài ai tăng gấp đôi nên sau khoảng 31 bước đã vượt k. Gọi m là chỉ số đầu tiên có độ dài >= k. Vì am có nửa đầu là a{m-1}, ta lùi dần: nếu vị trí pos nằm sau độ dài a{i-1} thì trừ đi độ dài đó. Bẫy: dùng long long cho độ dài và vị trí.
Nếu chỉ nộp sub này: đúng 28/28 test.
Chương trình hoàn chỉnh
Main đọc a (dạng chuỗi), n, k từ TIMSO.INP. Nếu k <= 255 gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
string s; // a_1 (chu so cua a)
long long n, k;
// Sub 1: vet can — chi giu k ky tu dau cua cac a_i, vi a_i = a_{i-1} a_{i-1}
// nen k ky tu dau cua a_i chi phu thuoc vao k ky tu dau cua a_{i-1}. Dung khi k <= 255.
void sub1() {
string pref = s;
for (long long i = 2; i <= n && (long long)pref.size() < k; i++) {
string t = pref + pref;
if ((long long)t.size() > k) t.resize(k);
pref = t;
}
cout << pref[k - 1] << "\n";
}
// Sub 2: do dai a_i tang gap doi moi buoc, nen chi can khoang 31 buoc.
// Tim buoc m dau tien co do dai >= k, roi "lan nguoc" vi tri k qua cac nua.
void sub2() {
vector<long long> len; // len[i-1] = do dai a_i
len.push_back((long long)s.size());
while (len.back() < k && (long long)len.size() < n)
len.push_back(len.back() * 2);
long long pos = k; // vi tri (1-based) can tim
for (int i = (int)len.size(); i >= 2; i--) {
long long L = len[i - 2]; // do dai a_{i-1}
if (pos > L) pos -= L; // nua sau cua a_i la a_{i-1} lan thu hai
}
cout << s[pos - 1] << "\n";
}
int main() {
freopen("TIMSO.INP", "r", stdin);
freopen("TIMSO.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> s >> n >> k;
if (k <= 255) sub1();
else sub2();
return 0;
}
Bình luận