Đếm Chữ Số
Đề bài
Bạn An đánh số trang cho một quyển sách có $N$ trang. Sau khi đánh số xong, bạn ấy hỏi các bạn các câu hỏi sau:
- Có bao nhiêu chữ số 0 mà bạn ấy đã sử dụng?
- Có bao nhiêu chữ số 1 mà bạn ấy đã sử dụng?
- …
- Có bao nhiêu chữ số 9 mà bạn ấy đã sử dụng?
Input
- Dòng đầu tiên là $T$ – số test.
- $T$ dòng tiếp theo, mỗi dòng là một số nguyên $N$.
- Chúng ta không quan trọng câu chuyện $N$ chẵn hay $N$ lẻ nhé.
Output
- In ra $T$ dòng, mỗi dòng gồm 10 số là số lượng chữ số 0, chữ số 1, …, chữ số 9 được sử dụng.
Giới hạn
- $1 \le T \le 1000$
- $1 \le N \le 10^6$
Subtask:
- 50% số test đầu tiên có $T \le 100$, $N \le 10^4$.
- 50% số test còn lại không có giới hạn gì thêm.
1
10 1 0 0 0 0 0 0 0 0Lờ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 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:
Đề bàiHiểu đúng đề: có T bộ test
Trước tiên mình giải thích rõ đề bài vì mình thấy nhiều bạn đọc không kỹ cứ làm nộp sai, đó là ta có $T$ bộ test các bạn nhé, và kết quả sẽ xuất ra $T$ dòng, mỗi dòng có 10 số là số lượng các chữ số từ 0 đến 9 nha các bạn. Ví dụ với bộ test input như sau thì kết quả sẽ xuất ra là:
3
5
10
150 1 1 1 1 1 0 0 0 0
1 2 1 1 1 1 1 1 1 1
1 8 2 2 2 2 1 1 1 1| Chữ số | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| N = 5 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| N = 10 | 1 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| N = 15 | 1 | 8 | 2 | 2 | 2 | 2 | 1 | 1 | 1 | 1 |
Giải thích: Dòng đầu tiên $N = 5$ thì từ 1 tới 5 ta sẽ có các chữ số 1, 2, 3, 4, 5 nên tại vị trí các chữ số này sẽ có số lượng là 1, còn các chữ số còn lại sẽ có số lượng là 0, nên ta có dòng kết quả tương ứng là: 0 1 1 1 1 1 0 0 0 0.
Dòng tiếp theo $N = 10$ thì từ 1 tới 10 sẽ là: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Từ 1 tới 9 sẽ là các chữ số từ 1 tới 9 đều xuất hiện 1 lần, đến số 10 thì chữ số 1 được xuất hiện thêm 1 lần nữa thành ra 2 lần, và có thêm xuất hiện của chữ số 0. Nên tóm lại với $N = 10$ thì có đủ các chữ số từ 0 đến 9 xuất hiện 1 lần, riêng chữ số 1 xuất hiện 2 lần, nên ta có dòng kết quả tương ứng là: 1 2 1 1 1 1 1 1 1 1.
Dòng tiếp theo $N = 15$ thì tương tự như mình đã phân tích ở 2 trường hợp $N = 5$, $N = 10$ ở trên các bạn tự suy ra hen (gợi ý: các số 11, 12, 13, 14, 15 góp thêm 6 chữ số 1 và mỗi chữ số 2, 3, 4, 5 thêm 1 lần).
Tại vì đề bài đưa ra ví dụ với $T = 1$ test case nên nhiều bạn chưa rành về vụ có nhiều bộ test thế này, vì thế mình thấy các bạn nộp sai nhiều.
Cách 1Vét cạn từng bộ test – O(T · N · log N)
Giờ ta bàn về cách giải quyết cho bài này. Thì một cách đơn giản nhất mà nhiều bạn sẽ nhìn thấy và làm đó là cứ cho vòng lặp chạy $T$ bộ test, với mỗi bộ test đọc số $N$ vào và chạy vòng lặp với giá trị $i$ từ 1 tới $N$, mỗi giá trị $i$ sẽ đi phân tích và đếm số lần xuất hiện của các chữ số từ 0 đến 9 của giá trị $i$ đó, và cứ thế cộng dồn hết lại; sau cùng khi vòng lặp $i$ kết thúc ta in ra kết quả số lượng của từng chữ số. Rồi cứ thế quy trình ở trên lặp lại qua bộ test tiếp theo.
Mảng đếm 10 phần tử thay cho 10 biến
Nói sâu hơn về việc mỗi giá trị $i$ cần đếm xem có bao nhiêu chữ số từ 0 đến 9 xuất hiện trong đó. Thì chỗ này bạn nào mà không có kinh nghiệm thì sẽ làm cách tạo ra 10 biến đếm tương ứng với 10 chữ số từ 0 đến 9, rồi sau đó phải xét 10 trường hợp if else (vd: if(digit == 0) cnt0++; else if(digit == 1) cnt1++; …). Như thế vẫn sẽ đúng nhưng rất dài dòng.
Một cách gọn nhất trong trường hợp này là ta sẽ tạo ra mảng có 10 phần tử để index tương ứng từ 0 đến 9, và nó cũng tương ứng là các chữ số từ 0 đến 9 luôn. Như thế a[i] hiểu là số lần xuất hiện của chữ số $i$. Ví dụ a[3] = 5 thì ta hiểu chữ số 3 xuất hiện 5 lần. Ban đầu mảng 10 phần tử khởi tạo tất cả giá trị là 0. Rồi cứ mỗi chữ số phân tích ra được từ số $i$ thì sẽ gọi a[digit]++;, tức là tăng thêm 1 tại vị trí a[digit]. Sau cùng thì ta duyệt vòng lặp từ 0 đến 9 và in ra các giá trị của mảng tại các vị trí đó thì đó là dãy đáp án.
Tách từng chữ số của một số
Về việc với từng số $i$ tiến hành đi phân tích ra từng chữ số của nó thì cái này quá cơ bản nhưng mình cũng nói luôn kẻo bạn nào không biết: với 1 số thì ta chia lấy dư cho 10 để lấy ra được chữ số cuối cùng của nó, ví dụ: 123 % 10 = 3. Rồi để lấy ra được chữ số tiếp theo thì ta phải loại bỏ đi chữ số mà ta vừa lấy ra bằng cách lấy số đó chia nguyên cho 10, ví dụ: 123 / 10 = 12 (vì cả 2 đều đang là số nguyên nên phép chia 2 số nguyên cho nhau kết quả sẽ ra số nguyên, chứ nếu 1 trong 2 mà là số thực thì kết quả phép chia sẽ là 12.3).
Rồi số còn lại là 12 thì ta lại lặp lại quy trình trên: 12 % 10 = 2, 12 / 10 = 1, 1 % 10 = 1, 1 / 10 = 0. Đến khi số là 0 rồi thì ta dừng quy trình vì từ bây giờ nó sẽ cứ lặp vô tận 0 % 10 = 0, 0 / 10 = 0, …
Source code để các bạn tham khảo với hướng làm mình trình bày ở trên:
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t--){
int n;
cin >> n;
int a[10] = {0};
for(int i = 1; i <= n; ++i){
int x = i;
while(x != 0){
a[x % 10]++;
x /= 10;
}
}
for(int i = 0; i < 10; ++i){
cout << a[i] << " ";
}
cout << endl;
}
return 0;
}import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
n = int(input())
a = [0] * 10
for i in range(1, n + 1):
x = i
while x != 0:
a[x % 10] += 1
x //= 10
print(*a)Giải thích một số chỗ trong code
- 2 dòng đầu tiên của hàm main (
ios::sync_with_stdio(false); cin.tie(0);): hiểu cơ bản là nó tăng tốc luồng nhập xuất của C++ (tắt đồng bộ với C và bỏ ràng buộc giữacinvàcout), giúpcin/coutchạy nhanh ngang cú pháp nhập xuất của C. Một kinh nghiệm trong các bài cần nhập xuất nhiều, ví dụ như bài này ta thấy có tối đa $T = 1000$ bộ test, nghĩa là ta sẽ cần xuất cả $10 \cdot 1000 = 10{,}000$ số (vì mỗi giá trị $N$ sẽ xuất 10 số), thì ta hãy nên để 2 dòng này vào để chạy nhanh hơn. Tất nhiên nếu các bạn code theo cú pháp của C thì chẳng cần mấy dòng đó làm gì, tuy nhiên thường khi code các bài lập trình thi đấu thế này ta dùng C++ vì cú pháp ngắn gọn cũng như nhiều hỗ trợ của nó, vậy nên bạn nào code C++ thì nhớ thêm 2 dòng này vào đầu hàm main nhé. while(t--)là viết gọn của "kiểm trat != 0rồi giảmt", tức là vòng lặp chạy đủ $t$ lần. Trong lập trình khi gọi 1 biến ra trong câu lệnh điều kiện mà không có so sánh gì, các bạn hiểu là đang so sánh khác 0 nhé, tức là:if(x)⇔if(x != 0). Cònif(!x)⇔if(x == 0).int a[10] = {0};nghĩa là khởi tạo mảng a 10 phần tử đều mang giá trị 0 hết. Nói chính xác hơn thì bản chất khi ta khởi tạo mảng= {0};thì nghĩa là gán giá trị 0 cho ô đầu tiên của mảng (a[0]), và nguyên tắc là chỉ cần có danh sách khởi tạo thì toàn bộ các ô còn lại không được ghi rõ sẽ mặc định giá trị 0. Nên nếu ô đầu tiên cũng được khởi tạo là 0 thì toàn bộ mảng đều có giá trị 0 hết nha các bạn.- Gán
x = i: với mỗi giá trị $i$ trong vòng lặp for thì ta phải gán nó qua biến $x$ rồi từ đó đi phân tích biến $x$, chứ ta không làm trực tiếp trên biến $i$, bởi vì thao tác chia nguyên cho 10 sẽ làm thay đổi giá trị biến $i$. Khi đó vòng for sẽ bị sai lệch: $i$ bị chia về 0, rồi++ithành 1, cứ thế $i$ luôn quanh quẩn ở giá trị 1 và vòng lặp for sẽ bị lặp vô tận. - Khởi tạo mảng bên trong vòng lặp T: bước
int a[10] = {0};ta phải để bên trong vòng lặp $T$ để với mỗi bộ test đọc vào sẽ reset lại mảng toàn giá trị 0, chứ nếu ta mà để nó bên trên vòng lặp $T$ thì các giá trị chữ số cứ thế sẽ bị cộng dồn liên tục sẽ bị sai nha các bạn.
Đánh giá độ phức tạp
Vòng lặp while chạy $T$ lần để đọc $T$ bộ test, với mỗi bộ test đọc vào giá trị $N$ thì sẽ khởi tạo mảng 10 phần tử 0, sau đó có vòng lặp for $i$ chạy từ 1 tới $N$, với mỗi giá trị $i$ lại chạy đủ bấy nhiêu lần số lượng chữ số của $i$ để phân tích ra. Sau cùng thì chạy vòng lặp 10 lần để in ra kết quả của test case đó. Vậy nên độ phức tạp sẽ là $O(T \cdot (10 + N \cdot \log X + 10))$, với $X$ là các số từ 1 đến $N$. Theo quy tắc cộng Big O thì giữa các thành phần cộng với nhau sẽ lấy theo thành phần lớn nhất nên ta có thể kết luận độ phức tạp là $O(T \cdot N \cdot \log X)$.
Tuy nhiên nếu bạn nào chưa nghĩ ra cách làm tối ưu thì cứ cài đặt theo cách bất kỳ, các bạn có thể giống như cách này chẳng hạn. Thậm chí theo mình là nên cài đặt theo cách này, để tuy nó chạy chậm nhưng nó luôn đảm bảo ra cho mình kết quả chính xác, từ đó ta có thể lấy nó làm công cụ kiểm tra tính chính xác cho một cách làm tối ưu khác tiếp theo (vét cạn + sinh test ngẫu nhiên rồi so sánh 2 cách).
Ý tưởngĐừng tính lại: a[N] = a[N − 1] + các chữ số của N
Lưu lại kết quả đã tính?
Giờ ta cần tìm ra một cách làm tốt hơn cho bài này. Ta cần nhìn thấy cách làm ở trên có cái dở là các giá trị $N$ nếu bị trùng nhau thì ta vẫn cứ phải đi tính lại. Tức là nếu giả sử trước đó ta đã xử lý tính ra kết quả của trường hợp $N = 10^6$ rồi, nếu bộ test tiếp theo đọc vào lại gặp $N = 10^6$ thì cách làm ở trên vẫn cứ đi xử lý lại, trong khi đó rõ ràng ta không cần phải xử lý lại vì ta đã tính ra trước đó kết quả của trường hợp này rồi mà. Vậy nên rõ ràng một cách để tốt hơn đó là ta có thể lưu trữ lại các kết quả $N$ đã tính, để mỗi giá trị $N$ mới ta có thể kiểm tra ngay trong $O(1)$ (nhờ vào kỹ thuật mảng đánh dấu) xem kết quả của trường hợp $N$ đó mình đã từng tính chưa. Nếu tính rồi thì ta lấy ra kết quả in ra thôi, khỏi phải đi xử lý.
Tuy nhiên việc tối ưu ở trên cũng chưa thực sự giải quyết được vấn đề. Giả sử $T$ bộ test toàn bộ đều là các giá trị phân biệt khác nhau thì với mỗi giá trị ta vẫn đều phải đi tính như bình thường. Ví dụ khi $T = 1000$ và các giá trị $N$ lần lượt từ $10^6$ trở về $999{,}001$ ($N = 1{,}000{,}000$, $N = 999{,}999$, $N = 999{,}998$, …) thì mọi giá trị $N$ ta đều phải đi tính chứ không có kết quả sẵn. Lúc này cứ căn cứ $N$ theo giá trị nhỏ nhất thì số lần lặp vẫn cỡ $1000 \cdot 999{,}000 \cdot 6 \approx 6$ tỷ lần lặp. Như thế cũng vẫn sẽ bị TLE thôi vì đã quá 100 triệu.
Mấu chốt: kết quả của N nằm sẵn trong kết quả của N − 1
Ta phải nhìn ra mấu chốt như sau: có phải nếu ta đã có kết quả thống kê số lượng các chữ số từ 0 đến 9 của trường hợp $N = 100$ rồi, thì qua trường hợp $N = 101$ tính ra nó vẫn sẽ là kết quả của trường hợp $N = 100$, chỉ đi phân tích thêm số 101 được thêm 1 chữ số 0 và 2 chữ số 1, lấy nó cộng thêm vào kết quả đã có của $N = 100$ là ta có kết quả của trường hợp $N = 101$ đúng không các bạn?
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
|---|---|---|---|---|---|---|---|---|---|---|
| a[100] | 11 | 21 | 20 | 20 | 20 | 20 | 20 | 20 | 20 | 20 |
| + số 101 | +1 | +2 | ||||||||
| a[101] | 12 | 23 | 20 | 20 | 20 | 20 | 20 | 20 | 20 | 20 |
Tức là nếu trường hợp $N = 100$ ta đã có dãy kết quả là 11 21 20 20 20 20 20 20 20 20 thì với trường hợp $N = 101$ ta sẽ cộng thêm vào dãy đó ở chữ số 0 thêm 1 đơn vị và ở chữ số 1 thêm 2 đơn vị, ta sẽ có dãy kết quả mới của trường hợp $N = 101$ là 12 23 20 20 20 20 20 20 20 20. Tại sao lại như vậy? Vì với $N = 100$ nghĩa là thống kê các chữ số từ 1 đến 100, với $N = 101$ nghĩa là thống kê các chữ số từ 1 đến 101, thì tính ra trường hợp $N = 101$ chỉ là có thêm số 101, còn lại từ số 1 đến 100 thì y như trường hợp $N = 100$.
Ở trên là điểm mấu chốt, khi ta đã nhìn ra được rồi thì sẽ dễ dàng nhìn ra tư tưởng giải quyết cho bài này. Để tính ra trường hợp $N$ thì ta cần có kết quả từ trường hợp $N - 1$. Ta tiếp tục thấy $N$ lớn nhất là $10^6$ và nhỏ nhất là 1 theo như giới hạn đề bài. Vậy có phải ta đi tính ra các kết quả của các trường hợp từ 1 đến $10^6$ thì ta chỉ chạy vòng lặp đủ $10^6$ lần là có đủ kết quả các trường hợp $N$ từ 1 đến $10^6$ đúng không các bạn? Bước xử lý phân tách các chữ số của $N$ cứ cho rằng lớn nhất là có 6 chữ số thì bước này lặp 6 lần, và mỗi kết quả là dãy 10 số sẽ được gán qua cho trường hợp mới, nên cả thảy ta chỉ tính $10^6 \cdot (10 + 6) = 1.6 \cdot 10^7$ lần lặp và lưu trữ hết vào trong mảng 2 chiều a có $10^6$ dòng, 10 cột. Rồi sau đó chạy vòng lặp $T$ bộ test, với mỗi bộ test đọc vào số $N$ thì ta gọi a[N] chính là dãy 10 kết quả của trường hợp $N$.
Như thế thì số lần lặp cả thảy của bài chỉ là $1.6 \cdot 10^7 + T \cdot 10$, với trường hợp xấu nhất $T = 1000$ thì số lần lặp sẽ là $16{,}010{,}000$ (16 triệu + 10 ngàn) lần lặp. Như thế này sẽ yên tâm không bị TLE vì nó nhỏ hơn ngưỡng giới hạn 100 triệu, cụ thể ít hơn cả 6 lần. Việc tạo mảng 2 chiều a có $10^6$ dòng, 10 cột là cách dùng kỹ thuật mảng đánh dấu để sau đó mỗi khi gặp giá trị $N$ ta chỉ cần gọi a[N] trong $O(1)$ là ra kết quả ngay lập tức.
Mô phỏng ý tưởng
Em nhập $N$ (tối đa 60) rồi bấm Tiếp để xem từng dòng $a[i]$ được chép từ $a[i - 1]$ rồi cộng thêm các chữ số của $i$:
Cách 2Tính trước a[1..10⁶] – AC
Source code để các bạn tham khảo với hướng làm mình trình bày ở trên:
#include <bits/stdc++.h>
using namespace std;
void PrintArray(const vector<int> &x){
for(int i = 0; i < (int)x.size(); ++i){
cout << x[i] << " ";
}
cout << endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
vector<vector<int>> a(1000001, vector<int>(10, 0));
for(int i = 1; i <= 1000000; ++i){
a[i] = a[i - 1];
int x = i;
while(x != 0){
a[i][x % 10]++;
x /= 10;
}
}
int t;
cin >> t;
while(t--){
int n;
cin >> n;
PrintArray(a[n]);
}
return 0;
}import sys
input = sys.stdin.readline
def PrintArray(x):
print(*x)
# precompute
a = [[0] * 10 for _ in range(1_000_001)]
for i in range(1, 1_000_001):
# copy previous row
a[i] = a[i - 1].copy()
x = i
while x != 0:
a[i][x % 10] += 1
x //= 10
t = int(input())
for _ in range(t):
n = int(input())
PrintArray(a[n])Giải thích một số chỗ trong code
vector<vector<int>> a(1000001, vector<int>(10, 0));nghĩa là khởi tạo vector 2 chiềuacó 1,000,001 dòng và mỗi dòng có 10 cột mang giá trị mặc định là 0. Lý do phải khởi tạo 1,000,001 dòng là để index chạy từ 0 đến 1,000,000 (do index tính từ 0), coi như ta bỏ qua không dùng dòng index 0, chỉ dùng từ 1 đến 1 triệu. Ta làm thế vì đề cho $N$ tính từ 1, nên để thống nhất tránh cứ phải rắc rối tính $N - 1$, tốn thêm 10 ô nhớ mà không bị rối rắm có thể dẫn đến sai. (Dòng 0 toàn số 0 cũng chính là điểm xuất phát $a[0]$ cho công thứca[i] = a[i - 1].)- Vì sao dùng vector thay vì mảng thường? Có nhiều lý do. Đầu tiên mảng cần có đến cả 10 triệu phần tử thì không thể khai báo
int a[1000001][10]bên trong hàm main được vì sẽ bị tràn bộ nhớ stack, phải dùng con trỏ cấp 2 để cấp phát mảng động, hoặc nếu không thì đưa mảng ra ngoài hàm main làm biến toàn cục thì mới được. Còn nếu trong hàm main mà đểint a[1000001][10]các bạn thử chạy trên máy đi sẽ thấy bị tắt chương trình luôn nhé. Tiếp theo đó do ta cần liên tục copy dãy 10 số kết quả của trường hợp $N - 1$ sang trường hợp $N$, nếu dùng vector sẽ rất tiện, chỉ cần làm phép gána[N] = a[N - 1]thì nó sẽ tự lấy từng phần tử của mảng này gán qua từng phần tử của mảng kia. Nếu dùng mảng thường thì ta phải làm vòng lặp chạy 10 lần để gán qua. Nói chung là gọn hơn được chút xíu ở khâu cài đặt ^^ - Hàm
PrintArray(const vector<int> &x): để cho gọn thì việc in ra dãy 10 số kết quả ta viết hàmPrintArraynhận tham số đầu vào là vector 1 chiều rồi in ra giá trị các phần tử. Bình thường lẽ ra chỉ cần làvector<int> xthôi đúng không các bạn? Nhưng tại sao lại có thêmconst &? Khi truyền tham chiếu (có&) thì sẽ không phải tạo bản sao dữ liệu; ở đây dữ liệu là mảng 10 phần tử thì có&sẽ không phải sao chép 10 phần tử mỗi lần gọi, mà ta có $T$ tối đa 1000 lần nên sẽ tiết kiệm cả 10,000 câu lệnh gán. Còn có thêmconstlà vì nếu để tham chiếu&, lỡ ta vô tình thay đổi giá trị của nó bên trong hàm (trong khi hàm chỉ cần xuất ra giá trị đâu cần thay đổi gì) thì nó bị thay đổi lại luôn dưới hàm main. Từ khoáconstràng buộc để nếu ta vô tình thay đổi giá trị thì trình biên dịch sẽ báo lỗi ngay, vìconstxem đó là hằng không thể thay đổi giá trị được.
Đánh giá độ phức tạp
Không gian: bộ nhớ cố định 10 triệu phần tử kiểu int → 40 triệu byte (vì int là 4 byte) $/ 1024 \approx 39{,}062.5$ KB $/ 1024 \approx 38.14$ MB. Trong khi đó đề cho giới hạn 128 MB nên ngưỡng ta xài ít hơn cả 3 lần, yên tâm ta sẽ không bị lỗi MLE (Memory Limit Exceeded: quá giới hạn bộ nhớ). (Thực tế mỗi dòng vector còn tốn thêm phần quản lý nên mình đo được khoảng 71 MB, vẫn dư sức.)
Thời gian: như đã phân tích ở cuối phần ý tưởng, khoảng $1.6 \cdot 10^7 + 10 \cdot T$ phép tính.
