Số Lượng Cách Xóa
Đề bài
Cho số tự nhiên $N$. Bằng cách giữ nguyên hoặc xoá đi một số chữ số liên tiếp của $N$ (nhưng không xoá hết) ta nhận được một số mới; nếu số $N$ bị chia thành 2 phần thì số mới được ghép lại từ hai phần này và giữ nguyên trật tự.
Yêu cầu: hãy xác định tất cả số cách xoá như trên để số $N$ mới sau khi xoá chia hết cho 3. Lưu ý là hai vị trí khác nhau sẽ tạo ra hai cách xoá khác nhau. Số $N$ giữ nguyên cũng được coi là một cách xoá.
Dữ liệu vào: số nguyên dương $N$ (không quá $10^5$ chữ số).
Dữ liệu ra: ghi ra một số nguyên là số cách xoá tìm được.
Giới hạn
- Có 50% số test có số các chữ số của $N \le 300$.
- Có 25% số test tiếp theo có số các chữ số của $N \le 10^4$.
- Có 25% số test còn lại có số các chữ số của $N \le 10^5$.
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| 1005 | 4 | Các số mới là: 1005, 105, 105, 15 |
| 2009 | 3 | Các số mới là: 009, 09, 9 |
Lời mở đầu
Bài này mình được một em học viên hỏi và mình đã hướng dẫn chi tiết cách thức giải quyết cho em ấy. Tin rằng sẽ có giá trị với nhiều bạn nên mình chia sẻ đề bài để các bạn thử sức làm, kèm thêm đó là toàn bộ tin nhắn của mình với em ấy để bạn nào không giải quyết được thì có thể tham khảo nhen. Hi 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:
Gợi ý2 kiến thức cần có
Ok, cần 2 kiến thức để làm:
- Kiến thức về prefix sum (mảng cộng dồn): cứ tính tổng cộng dồn, rồi khi cần biết tổng trong đoạn từ $L$ đến $R$ thì gọi
prefixSum[R] - prefixSum[L-1], cái này thì em biết rồi hen. - Kiến thức về các phép toán chia dư:
(a + b) % c = ((a % c) + (b % c)) % cKhông có phép chia nhé, chỉ có cộng, trừ, nhân.
(a − b) % c = ((a % c) − (b % c)) % c
(a · b) % c = ((a % c) · (b % c)) % c
Thì trong bài này là cần chia dư cho 3 (% 3) để xem kết quả có bằng 0 không. Vấn đề là chuỗi có chiều dài rất lớn (tới $10^5$ chữ số), không thể nào chuyển chuỗi đó về số rồi dùng phép % được, mà phải dựa theo tính chất: tổng các chữ số mà chia hết cho 3 thì số đó chia hết cho 3. Điều này dễ nhận ra thôi, em cứ lấy số 3 nhân với một số bất kỳ rồi cộng tổng các chữ số của kết quả lại, sẽ thấy tổng đó chia hết cho 3. Ví dụ $3 \times 123987 = 371961$, tổng $3 + 7 + 1 + 9 + 6 + 1 = 27$ chia hết cho 3.
75%Cách vét cạn: thử mọi đoạn xoá – O(n²)
Có phải em sẽ nhận ra cách làm vét cạn là gì: ví dụ chuỗi có chiều dài 4, tức là index từ 0 đến 3, thì sẽ xét các đoạn liên tiếp từ $i$ đến $j$ để xoá như sau: (0,0), (0,1), (0,2), (0,3), (1,1), (1,2), (1,3), (2,2), (2,3), (3,3). Lưu ý không lấy trường hợp (0,3) vì đề có nói không cho xoá hết toàn bộ chuỗi.
Với mỗi đoạn, em tính sum là tổng toàn bộ chữ số của chuỗi ban đầu, sau đó trừ đi tổng đoạn bị xoá, rồi xem phần còn lại có chia hết cho 3 không:
Bảng dưới đây là toàn bộ các cách xoá của ví dụ $N = 1005$, có đúng 4 cách cho ra số chia hết cho 3:
| Đoạn xoá | N (gạch = bị xoá) | Số mới | Tổng chữ số | Chia hết 3 |
|---|---|---|---|---|
| giữ nguyên | 1005 | 1005 | 6 | ✔ |
| i = 0, j = 0 | 1005 | 005 | 5 | |
| i = 0, j = 1 | 1005 | 05 | 5 | |
| i = 0, j = 2 | 1005 | 5 | 5 | |
| i = 1, j = 1 | 1005 | 105 | 6 | ✔ |
| i = 1, j = 2 | 1005 | 15 | 6 | ✔ |
| i = 1, j = 3 | 1005 | 1 | 1 | |
| i = 2, j = 2 | 1005 | 105 | 6 | ✔ |
| i = 2, j = 3 | 1005 | 10 | 1 | |
| i = 3, j = 3 | 1005 | 100 | 1 | |
| Số cách | 4 | |||
Cách vét cạn này là $O(\text{Length}_s^2)$, với độ dài $10^5$ thì quá chậm. Bài này có thể giải quyết với độ phức tạp $O(\text{Length}_s)$ nha em, tức là chỉ lặp $10^5$ lần là xong, đảm bảo trong 1 giây. Anh gợi ý đến đây rồi đó, ráng nghĩ tiếp em nhé, nếu vẫn không ra thì nói anh sẽ nói sâu thêm.
100%Cách tối ưu: đếm theo số dư – O(n)
Ok, vẫn chưa ra hả em, xem tiếp nhé:
Nếu nhóm sum + prefixSum[i-1] lại thành 1 nhóm gọi là $A$, và prefixSum[j] là $B$, thì giờ đây nó thành $A - B$. Để $A - B$ chia hết cho 3, tức là $(A - B) \% 3 = 0$. Còn nhớ phép toán chia lấy dư anh nói không? $(a - b) \% c$ $= ((a \% c) - (b \% c)) \% c$, với $c$ ở đây là 3, $a$ chính là $A$, $b$ chính là $B$.
Vậy em hiểu là sao? Là tính $A \% 3$, tức là (sum + prefixSum[i-1]) % 3 được bao nhiêu – cái này tính được vì sum đã có, prefixSum của từng vị trí mình cũng đã có. Kết quả khi % 3 chỉ có thể là 0, 1 hoặc 2:
- Giả sử $A \% 3 = 0$, thì để $(A - B) \% 3 = 0$, $B \% 3$ cũng phải bằng 0, để $0 - 0 = 0$.
- Nếu $A \% 3 = 1$ thì $B \% 3$ cũng phải bằng 1 để 2 thằng trừ nhau về 0. Tương tự với 2.
(sum + prefixSum[i-1]) % 3. Thì từ vị trí $j = i$ đến cuối dãy có bao nhiêu vị trí mà prefixSum[j] % 3 cũng bằng $x$, thì có bấy nhiêu cách xoá đoạn bắt đầu tại $i$ thỏa mãn. Ta chỉ cần 1 mảng cnt[3] đếm số vị trí $j$ (từ $i$ trở về sau) có prefixSum[j] % 3 bằng 0, 1, 2.Em nhập số $N$ rồi bấm Tiếp để xem từng bước: với mỗi vị trí bắt đầu xoá $i$, tính $x$ = (sum + prefixSum[i-1]) % 3 rồi đếm các vị trí $j \ge i$ có prefixSum[j] % 3 = x (ô xanh), kèm luôn các số mới tạo ra:
Source code theo đúng tư tưởng anh đã nói ở trên, đã nộp AC trên web, em tham khảo hen:
#include <bits/stdc++.h>
using namespace std;
long long solve(string &s){
s = " " + s;
long long prefixSum[s.length()] = {0}, sum = 0;
int cnt[3] = {0};
for(int i = 1; i < s.length(); ++i){
int digit = s[i] - '0';
sum += digit;
prefixSum[i] = prefixSum[i - 1] + digit;
cnt[prefixSum[i] % 3]++;
}
long long res = 0;
for(int i = 1; i < s.length(); ++i){
res += cnt[(sum + prefixSum[i - 1]) % 3];
cnt[prefixSum[i] % 3]--;
}
if(sum % 3 != 0){
res--;
}
return res;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
string s;
cin >> s;
cout << solve(s);
return 0;
}def solve(s):
s = " " + s
prefix_sum = [0] * len(s)
total_sum = 0
cnt = [0, 0, 0]
for i in range(1, len(s)):
digit = int(s[i])
total_sum += digit
prefix_sum[i] = prefix_sum[i - 1] + digit
cnt[prefix_sum[i] % 3] += 1
res = 0
for i in range(1, len(s)):
res += cnt[(total_sum + prefix_sum[i - 1]) % 3]
cnt[prefix_sum[i] % 3] -= 1
if total_sum % 3 != 0:
res -= 1
return res
s = input().strip()
print(solve(s))Vì sao lại có dòng cnt[prefixSum[i] % 3]--?
Em cứ lấy vài cái ví dụ chạy tay quy trình logic code xử lý là em sẽ hiểu rõ nha. Ban đầu mảng cnt đang đếm cho toàn bộ các vị trí $j$ từ 1 đến $n$. Ở vị trí $i$, ta cộng vào đáp án cnt[(sum + prefixSum[i - 1]) % 3], tức là số vị trí $j \ge i$ thỏa mãn. Rồi khi tiếp tục i++ để xét vị trí $i$ mới, thì vị trí $j = i$ cũ không còn hợp lệ nữa (vì $j$ phải $\ge i$ mới), nên phải trừ nó ra khỏi mảng cnt, em hình dung chưa nè.
Vì sao cuối cùng lại có if(sum % 3 != 0) res--?
Em xem nhé, đề không cho xoá hết, nên trường hợp $i = 1$, $j = n$ là không được lấy đúng không? Tuy nhiên code ở trên vẫn cứ tính tất cả mọi trường hợp kể cả trường hợp đó. Khi đó prefixSum[i-1] = prefixSum[0] = 0, còn prefixSum[n] chính là sum, nên $sum - sum = 0$ luôn chia hết cho 3, tức là nó luôn bị tính thêm 1 lần vào đáp án.
Sau đó đề bài có nói: giữ nguyên chuỗi ban đầu (không xoá gì) vẫn xem là 1 cách xoá. Vậy nếu sum chia hết cho 3 thì phải tính thêm 1 lần vào đáp án; mà đáp án vốn đã bị cộng dư 1 lần như anh nói ở trên rồi, nên khi sum chia hết cho 3 thì xem như không làm gì cả. Còn nếu sum không chia hết cho 3 thì đáp án không được cộng thêm, nhưng nó đã bị cộng dư 1 trước đó, nên lúc này phải trừ đi 1 thì mới chính xác. Nói chung để code rõ nghĩa hơn thì chỗ đó có thể viết thế này:
res--;
if(sum % 3 == 0){
res++;
}Tức là res cứ giảm đi 1 trước đã vì đề không cho xoá hết, rồi sau đó nếu sum chia hết cho 3 thì vẫn tính vào đáp án vì đề nói rõ không xoá gì thì vẫn là 1 cách xoá.
Mình đã kiểm tra cả 2 bản code với 300 số ngẫu nhiên so với cách vét cạn, đều cho cùng kết quả; với $N$ dài $10^5$ chữ số, bản C++ chạy chưa tới 0.01 giây, bản Python khoảng 0.06 giây. Lưu ý đáp án có thể lên tới khoảng $n^2 / 2 \approx 5 \cdot 10^9$, vượt int, nên res phải để kiểu long long như trong code nhé.
Nhận xét
Đăng nhận xét