Tìm Ký Tự Thứ K
Đề bài
Cho một xâu ký tự có độ dài $n$, từ xâu này có thể tạo ra một xâu ký tự dài vô tận bằng cách lặp lại thao tác sau: xét xâu $s_1$, lấy ký tự cuối cùng của xâu đó đảo lên đầu, ta được một xâu mới là $s_2$; sau đó ghép xâu $s_2$ vào cuối xâu $s_1$ ta được một xâu $s$ mới. Ví dụ:
Nhiệm vụ của Grenore là tìm ký tự thứ $k$ trong xâu này. Do chỉ được thử một lần, Grenore muốn nhờ các bạn tìm giúp cậu.
Dữ liệu vào
- Dòng đầu tiên gồm một số nguyên $k$ ($1 \le k \le 10^{18}$).
- Dòng thứ hai chứa một xâu ký tự $s$ ($1 \le |s| \le 30$), $s$ chỉ bao gồm các chữ cái viết hoa.
Dữ liệu ra: một ký tự duy nhất là ký tự thứ $k$ xuất hiện trong xâu.
8
RYUUU8
ABCALời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesLộ trình lời giải, bấm vào từng phần để nhảy tới:
Chưa đạtCách 1: sinh chuỗi theo đúng quy luật
Một cách xử lý đơn giản nhất mà ta dễ dàng nhìn ra là làm theo đúng quy luật của đề bài: nếu $k$ lớn hơn độ dài chuỗi $s$ thì cứ sinh ra chuỗi $s$ mới theo quy tắc đề bài, đến khi nào $k \le$ độ dài chuỗi $s$ thì ký tự cần tìm chính là s[k - 1].
Xem code sinh chuỗi (bị MLE/TLE)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
long long k;
cin >> k;
string s;
cin >> s;
while(k > (long long)s.length()){
string t = s;
s.push_back(t.back());
t.pop_back();
s += t;
}
cout << s[k - 1];
return 0;
}import sys
k, *rest = sys.stdin.read().split()
k = int(k)
s = rest[0]
while k > len(s):
t = s
s += t[-1]
t = t[:-1]
s += t
print(s[k - 1])Giải thích: vòng lặp lặp liên tục khi k > s.length(), nghĩa là chuỗi $s$ chưa chứa được ký tự tại vị trí $k$. Ta tạo chuỗi t lưu giá trị hiện tại của $s$. Đề bài mô tả là đem ký tự cuối cùng lên đầu rồi nối vào sau chuỗi hiện tại; ta không nhất thiết phải xoá rồi chèn vào đầu (vì chèn vào đầu thì toàn bộ phần tử phải nhích xuống), mà cho $s$ nhận ký tự cuối của t trước, sau đó t bỏ ký tự cuối đi rồi nối t vào sau $s$. Kết quả vẫn y hệt:
s.push_back(t.back());– thêm ký tự cuối cùng củatvào cuối $s$.t.pop_back();– xoá ký tự cuối cùng củat.s += t;– nối chuỗitvào đằng sau chuỗi $s$.
Độ phức tạp không gian: chuỗi bản chất là mảng 1 chiều các ký tự, để ra kết quả thì chuỗi $s$ phải chứa ít nhất $K$ ký tự, nên là $O(K)$. Trường hợp xấu nhất $K = 10^{18}$ thì cần $10^{18}$ byte bộ nhớ (mỗi ký tự char chiếm 1 byte), chắc chắn bị lỗi MLE (Memory Limit Exceeded). Thậm chí chạy trên máy tính của các bạn thì chương trình bị tắt luôn. Các bạn thử tính nhé, 1 KB = 1024 byte, 1 MB = 1024 KB, 1 GB = 1024 MB:
Sơ sơ là hơn 931 triệu GB! Ví dụ phổ thông ta hay mua ổ cứng 500 GB thì phải cần hơn 1 triệu 8 trăm ngàn cái ổ cứng như vậy mới lưu hết. Các bạn thấy kinh khủng chưa?
Độ phức tạp thời gian: chuỗi sinh ra theo nguyên tắc gấp đôi lên nên vòng while chỉ lặp $O(\log_2 K)$ lần; push_back, pop_back là $O(1)$; nhưng s += t là $O(N)$ với $N$ là độ dài t, cộng lại toàn bộ các lần nối là $O(K)$. Với $K = 10^{18}$ thì quá ngưỡng $10^8$ nên chắc chắn cũng TLE. Vậy cách làm này không ổn chút nào rồi.
100%Cách 2: chia để trị – lần ngược vị trí K
Ta cần tìm ký tự tại vị trí thứ $K$ (tính từ 1, từ trái qua phải) nhưng không thể đi tạo ra chuỗi được. Để giải quyết bài này ta dùng phương pháp chia để trị (divide and conquer). Hãy xét chuỗi ban đầu là "ABC", qua các phép biến đổi ta được (L là độ dài chuỗi):
| L | Chuỗi (phần in đậm là chuỗi s₂ vừa ghép vào) |
|---|---|
| 3 | ABC |
| 6 | ABCCAB |
| 12 | ABCCABBABCCA |
| 24 | ABCCABBABCCAAABCCABBABCC |
Nếu $K \le 3$ (độ dài chuỗi gốc) thì ta biết ngay đáp án là s[K - 1]. Còn nếu $K > 3$, giả sử cần tìm vị trí $K = 22$: nó thuộc chuỗi có $L = 24$. Nhưng các bạn thử lần ngược lại đi: nó chính là ký tự đứng ở vị trí thứ 9 của chuỗi $L = 12$; lần ngược tiếp, nó là ký tự ở vị trí thứ 2 của chuỗi $L = 6$; mà $2 \le 3$ nên đáp án là s[1], tức là ký tự B.
Tại sao lần ngược được như vậy? Vì chuỗi mới có độ dài gấp đôi chuỗi cũ: nửa đầu chính là chuỗi cũ, còn nửa sau là chuỗi cũ bị "xoay" 1 ký tự (ký tự cuối lên đầu). Nên vị trí thứ $p$ trong nửa sau (tính từ đầu nửa sau) ứng với vị trí $p - 1$ của chuỗi cũ, riêng $p = 1$ là ký tự cuối cùng của chuỗi cũ.
s[K - 1].Vì sao khi $K = 0$ thì gán lại $K = X$? Vì $K = 0$ nghĩa là trước khi trừ đi 1 thì $K$ là vị trí 1 của nửa sau, tức ký tự đầu tiên của chuỗi mới được sinh ra – mà ký tự đó chính là ký tự cuối cùng của chuỗi trước đó (vị trí $X$). Các bạn xem vài ví dụ với chuỗi "ABC" nhé:
K = 22:
| K | X lớn nhất < K | Cập nhật |
|---|---|---|
| 22 | 12 | 22 − 12 − 1 = 9 |
| 9 | 6 | 9 − 6 − 1 = 2 |
| 2 | — | K ≤ L = 3 ⇒ đáp án s[1] = B |
K = 20:
| K | X lớn nhất < K | Cập nhật |
|---|---|---|
| 20 | 12 | 20 − 12 − 1 = 7 |
| 7 | 6 | 7 − 6 − 1 = 0 ⇒ bằng 0 nên gán lại K = 6 |
| 6 | 3 | 6 − 3 − 1 = 2 |
| 2 | — | K ≤ L = 3 ⇒ đáp án s[1] = B |
K = 18:
| K | X lớn nhất < K | Cập nhật |
|---|---|---|
| 18 | 12 | 18 − 12 − 1 = 5 |
| 5 | 3 | 5 − 3 − 1 = 1 |
| 1 | — | K ≤ L = 3 ⇒ đáp án s[0] = A |
K = 17:
| K | X lớn nhất < K | Cập nhật |
|---|---|---|
| 17 | 12 | 17 − 12 − 1 = 4 |
| 4 | 3 | 4 − 3 − 1 = 0 ⇒ bằng 0 nên gán lại K = 3 |
| 3 | — | K ≤ L = 3 ⇒ đáp án s[2] = C |
Em nhập $K$ và xâu $s$ rồi bấm Tiếp để xem từng lần lần ngược: tìm $X$ lớn nhất nhỏ hơn $K$, thấy $K$ nằm ở nửa sau (màu cam), rồi đưa về vị trí tương ứng ở nửa đầu (màu xanh). Nếu chuỗi đủ ngắn mình vẽ luôn từng ký tự cho em kiểm tra:
Và $K = 15$: $15 - 12 - 1 = 2 \Rightarrow$ s[1] = B. Rồi đến đây các bạn đã rõ công thức làm bài này rồi hen.
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
long long k;
cin >> k;
string s;
cin >> s;
long long l = (long long)s.length();
while(k > l){
long long x = l;
while(x * 2 < k){
x *= 2;
}
k = k - x - 1;
if(k == 0){
k = x;
}
}
cout << s[k - 1];
return 0;
}import sys
k, *rest = sys.stdin.read().split()
k = int(k)
s = rest[0]
l = len(s)
while k > l:
x = l
while x * 2 < k:
x *= 2
k = k - x - 1
if k == 0:
k = x
print(s[k - 1])Giải thích: vòng lặp lặp liên tục nếu $K > L$, chỉ dừng khi $K \le L$ thì trả về s[K - 1]. Bên trong: tạo biến $X = L$, cứ nhân đôi $X$ nếu X * 2 < K để được giá trị $X$ lớn nhất nhỏ hơn $K$, rồi cập nhật $K = K - X - 1$; nếu $K$ bằng 0 thì gán lại $K = X$.
Độ phức tạp không gian: $O(N)$ với $N$ là độ dài chuỗi $s$ đầu vào, tối đa chỉ 30 ký tự nên yên tâm không bị MLE như cách trước hehe.
Độ phức tạp thời gian: vòng while trong cùng là $O(\log K)$, và giá trị $K$ liên tục giảm đi rất nhiều sau mỗi lần. Các bạn thử đặt biến đếm cnt trong vòng lặp trong cùng, chạy trường hợp xấu nhất $S$ = "A" ($L = 1$) và $K = 10^{18}$ thì thấy số lần lặp cả thảy chỉ khoảng 1 000 lần. Nên yên tâm không sợ bị TLE nhé các bạn. Lưu ý $X$ có thể lên tới gần $10^{18}$ nên X * 2 cỡ $2 \cdot 10^{18}$, vẫn nằm gọn trong long long.
Mình đã kiểm tra cả 2 cách (C++ và Python) với 300 bộ test ngẫu nhiên so với cách sinh chuỗi thật, đều cho cùng kết quả; với $K = 10^{18}$ cả 2 bản đều chạy tức thì.
Nhận xét
Đăng nhận xét