Tìm Chữ Số (CHUSO2)
Đề bài
CHUSO2 – Tìm chữ số · Giới hạn thời gian: 1.0 giây · Giới hạn bộ nhớ: 128 megabyte
Cho một số nguyên $N$ được tạo thành bằng cách viết liên tiếp tất cả các số từ $1$ đến $10^{15}$. Vậy các chữ số đầu tiên của $N$ là:
N = 1234567891011121314151617181920...
Hãy tìm chữ số thứ $p$ của $N$.
Dữ liệu nhập:
- Là số nguyên $p$ $(1 \le p \le 10^{15})$.
Dữ liệu xuất:
- Là chữ số thứ $p$ của $N$.
55110302Lờ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 😇. Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:
Link này công khai, bạ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 NTUCoderLộ trình lời giải, bấm vào từng phần để nhảy tới:
Cách 1Vét cạn: ghép từng số, đếm từng chữ số – O(p)
Một cách làm cơ bản nhất có thể nhìn ra ngay đó là vét cạn xét tuần tự, nghĩa là ta sẽ tạo ra chuỗi số được ghép liên tục từ các số tự nhiên tăng dần rồi với mỗi số ta xét đếm các chữ số của nó từ trái qua phải, mỗi lần như vậy tăng biến đếm lên. Khi nào đếm bằng với $p$ thì vòng lặp dừng lại, ngay lúc đó nó đang ở chữ số nào thì đó là kết quả; còn nếu đếm vẫn còn nhỏ hơn $p$ thì cứ ghép tiếp thêm số vào rồi lặp lại quy trình như trên.
Để cho đơn giản, mỗi số $x$ ta chuyển nó thành chuỗi để từ đó có thể nhanh chóng xét đến từng chữ số bên trong nó từ trái qua phải, chứ nếu để nó ở dạng số thì việc xét từng chữ số từ trái qua phải cũng đòi hỏi xử lý phức tạp.
Source code cho tư tưởng vét cạn trình bày ở trên để các bạn tham khảo:
Code vét cạn O(p) – chỉ dùng được khi p nhỏ
#include <bits/stdc++.h>
using namespace std;
int main(){
long long p, cnt = 0, x = 1;
cin >> p;
char res;
while(cnt < p){
string s = to_string(x);
for(int i = 0; i < (int)s.length(); ++i){
cnt++;
if(cnt == p){
res = s[i];
break;
}
}
x++;
}
cout << res;
return 0;
}p = int(input())
cnt = 0
x = 1
while cnt < p:
s = str(x)
for ch in s:
cnt += 1
if cnt == p:
res = ch
break
x += 1
print(res)Đánh giá độ phức tạp của cách làm này:
Với code ở trên, vòng lặp sẽ lặp đủ $p$ lần. Theo như giới hạn đề bài đưa ra, $p$ có thể lên đến tối đa là $10^{15}$, nếu trường hợp xấu nhất đó xảy ra thì chắc chắn code ở trên sẽ bị TLE. Thậm chí không cần phải là trường hợp xấu nhất đó nữa, bởi ta đã biết khi giới hạn thời gian là 1 giây thì số lần lặp tối đa để không bị TLE sẽ là $(3 \text{ đến } 5) \cdot 10^7$ hay cao lắm là $10^8$, nên chỉ cần $p$ lớn hơn $10^8$ thôi là code ở trên đã bị TLE rồi chứ chưa cần phải đến $10^{15}$.
Vậy nên code ở trên tuy ngắn gọn, đơn giản và không đòi hỏi tư duy nhiều nhưng nó không tối ưu. Nhưng ta vẫn cứ cài đặt nó để qua đó nhìn ra những cái không tốt của nó, làm cơ sở cho ta tìm ra một cách làm tối ưu hơn. Cũng nhờ code vét cạn đó mà ta có thể làm ra công cụ kiểm tra tính chính xác cho cách làm tối ưu (sinh test ngẫu nhiên rồi so kết quả 2 code).
Ý tưởngĐếm nhanh theo nhóm số có cùng số chữ số
Giờ ta đi thảo luận cách xử lý tối ưu cho bài này, nó chỉ cần các bạn vận dụng một chút tư duy toán học thôi mà hehe. Cái dở của code ở trên là nó cứ đi xét tuần tự các số tự nhiên rồi với từng số lại đi xét tuần tự từng chữ số của số đó. Trong khi đó ta không cần thiết phải nhọc công như vậy.
Hãy để ý rằng chuỗi $N$ là các số ghép liên tục bắt đầu từ $1$:
- Các số có 1 chữ số (từ 1 đến 9) cả thảy có $9 \cdot 1 = 9$ chữ số.
- Các số có 2 chữ số (từ 10 đến 99) có $99 - 10 + 1 = 90$ số, nên có $90 \cdot 2 = 180$ chữ số.
- Các số có 3 chữ số (từ 100 đến 999) có $900$ số, nên có $900 \cdot 3 = 2700$ chữ số.
- Cứ như thế, với các số có 4, 5, 6, 7, 8, 9 chữ số sẽ là: $36 \cdot 10^3$, $45 \cdot 10^4$, $54 \cdot 10^5$, $63 \cdot 10^6$, $72 \cdot 10^7$, $81 \cdot 10^8$... Tổng quát: nhóm số có $i$ chữ số đóng góp $\boxed{9 \cdot i \cdot 10^{i-1}}$ chữ số.
| Số chữ số $i$ | Các số | Bao nhiêu số | Số chữ số đóng góp | Cộng dồn |
|---|---|---|---|---|
| 1 | 1 → 9 | 9 | 9 | 9 |
| 2 | 10 → 99 | 90 | 180 | 189 |
| 3 | 100 → 999 | 900 | 2.700 | 2.889 |
| 4 | 1.000 → 9.999 | 9.000 | 36.000 | 38.889 |
| 5 | 10.000 → 99.999 | 90.000 | 450.000 | 488.889 |
| … | … | … | … | … |
| 14 | 10.000.000.000.000 → 99.999.999.999.999 | 90.000.000.000.000 | 1.260.000.000.000.000 | 1.388.888.888.888.889 |
Cộng dồn đến nhóm 14 chữ số đã vượt $10^{15}$ nên chỉ cần xét $i$ từ 1 đến 14.
Ví dụ p = 250
Giả sử ta cần tìm chữ số tại vị trí $p = 250$:
- $250 - 9 = 241 \ge 0$ → ta có thể bỏ qua các số có 1 chữ số.
- $241 - 180 = 61 \ge 0$ → bỏ qua tiếp các số có 2 chữ số.
- $61 - 2700$ ra số âm → chữ số thứ $p$ nằm trong đoạn của các số có 3 chữ số, tức là trong đoạn từ $100$ đến $999$, và nó là chữ số thứ $61$ của đoạn này.
Vậy chữ số đó thuộc về số nào cụ thể? Các số trong đoạn này đều có 3 chữ số, nên ta lấy $61 / 3 = 20$, $61 \,\%\, 3 = 1$. Vì phép chia lấy dư ra kết quả khác 0, nghĩa là đã đi hết trọn 20 số và còn lấn sang số bên cạnh. Vậy tính từ số $100$ là số thứ 1 thì số thứ 21 chính là số chứa vị trí thứ $p$, tức là số $100 + 21 - 1 = 120$, và chữ số cần tìm nằm tại vị trí thứ $1$ (vì $61 \,\%\, 3 = 1$) tính từ trái qua phải của số đó → đáp án là chữ số 1.
Nếu giả sử $p = 249$ thì sau khi bỏ qua các số có 1, 2 chữ số, phần còn lại là $60$: $60 / 3 = 20$, $60 \,\%\, 3 = 0$. Vì phần dư là 0 nên nó không lấn sang số tiếp theo mà dừng đúng ở số thứ 20 tính từ 100, tức là $100 + 20 - 1 = 119$, và chữ số cần tìm là chữ số cuối cùng của 119 → đáp án là 9.
cnt == p, trước dòng gán res = s[i] thì thử thêm 1 dòng cout << "x = " << x << endl; để xem ngay tại vị trí đó là đang xét số nào.Minh hoạNhảy qua từng nhóm số
Em nhập $p$ (tối đa $10^{15}$) rồi bấm Tiếp để xem từng bước: trừ dần số chữ số của từng nhóm, rồi tìm ra số chứa chữ số thứ $p$:
Cách 2Lưu số chữ số từng nhóm vào mảng a
Nếu đã nhìn ra quy luật ở trên rồi thì việc còn lại là cài đặt hiện thực ra thôi. Chỗ này nếu bạn nào không xử lý khéo thì cũng dài dòng phức tạp lắm đây.
Trước tiên ta cần một mảng 1 chiều $a$ lưu trữ lại số lượng chữ số của nhóm các số có 1, 2, 3, 4... chữ số, cụ thể là: $9 \cdot 10^0$, $18 \cdot 10^1$, $27 \cdot 10^2$, $36 \cdot 10^3$, $45 \cdot 10^4$... Thử nhẩm một chút trên máy tính: $p$ tối đa là $10^{15}$, nếu ta cứ cộng dồn $9 \cdot 10^0 + 18 \cdot 10^1 + 27 \cdot 10^2 + \ldots$ đến khi tổng vượt qua ngưỡng $10^{15}$ thì dừng, ta sẽ thấy cần lưu trữ đến mức $126 \cdot 10^{13}$, tức là mảng cần 14 phần tử (số mũ từ $10^0$ đến $10^{13}$).
Để cho thuận tiện, vì ta đang tính số lượng chữ số từ 1 trở đi, nên để trùng khớp với vị trí index thì ta cho mảng $a$ có 15 phần tử (index từ 0 đến 14), bỏ qua không dùng index 0: $a[i] = 9 \cdot i \cdot 10^{i-1}$ là số chữ số của nhóm các số có $i$ chữ số.
- Cho $i$ chạy từ 1: nếu $p - a[i] \ge 0$ thì trừ $p$ đi $a[i]$ và $i$++. Đến khi trừ ra số âm thì dừng: chữ số thứ $p$ nằm trong nhóm các số có $i$ chữ số, và nó là chữ số thứ $p$ (giá trị $p$ còn lại) của nhóm.
- Số đầu tiên có $i$ chữ số là $10^{i-1}$. Ta cho $x = 10^{i-1} + p/i - 1$ (ví dụ trên: $x = 100 + 61/3 - 1 = 119$).
- Xét $p \,\%\, i$: nếu khác 0 thì $x$++ (thành 120), đổi $x$ sang chuỗi và lấy ký tự tại index $(p \,\%\, i) - 1$ (phải trừ 1 vì index chuỗi tính từ 0).
- Nếu $p \,\%\, i = 0$ thì không cần $x$++, chữ số cần tìm là chữ số cuối cùng của $x$, lấy luôn bằng $x \,\%\, 10$, không cần mất công đổi $x$ sang chuỗi làm gì cả.
Source code cho tư tưởng trình bày ở trên để các bạn tham khảo:
#include <bits/stdc++.h>
using namespace std;
int main(){
long long p, a[15], i;
cin >> p;
for(i = 1; i <= 14; ++i){
a[i] = 9 * i * pow(10, i - 1);
}
i = 1;
while(p - a[i] >= 0){
p -= a[i];
i++;
}
long long x = (long long)pow(10, i - 1) + p/i - 1;
p %= i;
if(p == 0){
cout << x % 10;
}
else{
x++;
string s = to_string(x);
cout << s[p - 1];
}
return 0;
}p = int(input())
a = [0] * 15
for i in range(1, 15):
a[i] = 9 * i * (10 ** (i - 1))
i = 1
while p - a[i] >= 0:
p -= a[i]
i += 1
x = (10 ** (i - 1)) + (p // i) - 1
p %= i
if p == 0:
print(x % 10)
else:
x += 1
s = str(x)
print(s[p - 1])Đánh giá độ phức tạp của cách làm này:
Vòng lặp đầu chạy 14 lần để tạo ra mảng $a$, bên trong có dùng hàm pow để tính $10^{i-1}$ (cỡ $O(\log i)$). Vòng while tìm nhóm trong trường hợp xấu nhất cũng chỉ chạy 14 lần. Tính $10^{i-1}$ để tạo ra $x$ mất $O(\log i)$, đổi $x$ sang chuỗi mất $O(L)$ với $L$ là số chữ số của $x$. Còn các phép chia, trừ, chia lấy dư, truy xuất index trong chuỗi đều là $O(1)$. Theo quy tắc cộng Big-O thì lấy thành phần lớn nhất: $O(N \cdot \log i)$ với $N = 14$ là số phần tử mảng $a$.
Mà $N$ tối đa 14, $\log_2 14$ coi như là 4, nên $N \cdot \log i$ chỉ cỡ $14 \cdot 4 = 56$ phép tính. Vậy nên chắc chắn cách này không thể nào bị TLE được, trong phạm vi giới hạn của bài thì độ phức tạp này gần như là hằng số luôn rồi, mà độ phức tạp hằng số là tối ưu nhất rồi các bạn nhé.
Cách 3Bỏ luôn mảng a, gộp vào 1 vòng for
Thực ra đoạn code ở trên ta có thể tối ưu thêm nữa, ngay từ đầu mình cũng muốn trình bày luôn nhưng sợ gộp nhiều quá các bạn sẽ khó hiểu nên phần này mới nói sau.
- Bước đầu tiên tạo ra mảng $a$ có đủ 14 phần tử, trong khi có thể $p$ không đủ lớn để cần đến 14 phần tử như vậy. Lỡ ví dụ $p$ chỉ là 5 thì việc tạo ra 14 phần tử là không cần thiết.
- Và ta có cần thiết phải lưu các giá trị đó vào mảng không? Sau cùng chỉ là lấy $p$ trừ cho các giá trị đó đến khi nào trừ mà ra số âm thì dừng lại, rồi lấy vị trí $i$ đó mà đi tính tiếp, lúc đó chẳng cần $a[i]$ làm gì cả.
Vậy ta cho vòng lặp chạy $i$ từ 1 đến 14, tính ra giá trị $x = 9 \cdot i \cdot 10^{i-1}$ ngay tại chỗ, nếu $p$ trừ được thì trừ, không trừ được thì break kết thúc. Mọi thứ còn lại y như code trước đó.
#include <bits/stdc++.h>
using namespace std;
int main(){
long long p, x, i;
cin >> p;
for(i = 1; i <= 14; ++i){
x = 9 * i * pow(10, i - 1);
if(p - x >= 0){
p -= x;
}
else{
break;
}
}
x = (long long)pow(10, i - 1) + p/i - 1;
p %= i;
if(p == 0){
cout << x % 10;
}
else{
x++;
string s = to_string(x);
cout << s[p - 1];
}
return 0;
}p = int(input())
for i in range(1, 15):
x = 9 * i * (10 ** (i - 1))
if p - x >= 0:
p -= x
else:
break
x = (10 ** (i - 1)) + (p // i) - 1
p %= i
if p == 0:
print(x % 10)
else:
x += 1
s = str(x)
print(s[p - 1])Lúc này độ phức tạp không gian đã được cải tiến so với code trước, giờ chỉ là $O(1)$:
Còn về thời gian thì được tối ưu hơn code trước ở chỗ không cần vòng lặp while riêng mà đã gộp luôn vào vòng lặp for đầu tiên. Trường hợp xấu nhất khi $p$ rất lớn cỡ $10^{15}$ thì cũng tương tự code trước, nhưng khi $p$ không quá lớn thì code này nhanh hơn nhiều vì không phải cứ xét đủ 14 lần mà có thể dừng sớm. Và code này về mặt trình bày cũng gọn hơn các bạn thấy không?
