Cặp Số Chia Hết Cho 3 (BAI3)

Nguồn: Đề thi (BAI3) Độ khó: Trung bình Số học Chia lấy dư Mảng đánh dấu

Đề bài

Bài 3: Cặp số chia hết cho 3

Với hai số nguyên dương $u, v$, khi viết số $v$ sau số $u$ ta được một số mới.

Ví dụ: $u = 99$, $v = 123$, khi viết số $v$ sau số $u$, ta được số mới là số $99123$.

Cho $n$ số nguyên dương $a_1, a_2, \ldots, a_n$ và $m$ số nguyên dương $b_1, b_2, \ldots, b_m$. Với mỗi giá trị $b_i$ $(1 \le i \le m)$, bạn hãy cho biết có bao nhiêu số $a_j$ $(1 \le j \le n)$ sao cho khi viết $a_j$ sau $b_i$ được một số mới chia hết cho 3?

Dữ liệu: vào từ file văn bản BAI3.INP

• Dòng đầu chứa hai số nguyên dương $n, m$ $(1 \le n, m \le 100000)$.
• Dòng tiếp theo chứa $n$ số nguyên dương $a_1, a_2, \ldots, a_n$ $(a_i \le 10^8,\ 1 \le i \le n)$.
• Dòng tiếp theo chứa $m$ số nguyên dương $b_1, b_2, \ldots, b_m$ $(b_i \le 10^8,\ 1 \le i \le m)$.

Kết quả: ghi ra file văn bản BAI3.OUT trên $m$ dòng, dòng thứ $i$ ghi số lượng số $a_j$ $(1 \le j \le n)$ sao cho khi viết $a_j$ sau $b_i$ được một số mới chia hết cho 3.

Ràng buộc: 60% số test tương ứng với 60% số điểm có $1 \le n, m \le 1000$.

(Khi chạy thử/nộp trên hệ thống chấm online thì đọc dữ liệu từ bàn phím và in ra màn hình như code trong bài.)

BAI3.INP

5 2
123 4 5 7 10
3 2

BAI3.OUT

1
3

Giải thích: $b_1 = 3$, có duy nhất một số $a_1$ khi viết sau $b_1$ tạo thành số $3123$ chia hết cho 3. $b_2 = 2$, có ba số $a_2, a_4, a_5$ khi viết sau $b_2$ tạo thành các số $24, 27, 210$ chia hết cho 3.

Lời mở đầu

Bài này mình được một bạ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ài này rất hay để thấy được cái "đã" của giải thuật: từ hơn 10 tỷ lần lặp rút xuống chỉ còn 200 ngàn lần, mà code còn ngắn hơn nữa.

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ộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Giải thích thêm ví dụ: với $b_1 = 3$, ta lần lượt ghép từng $a_j$ vào sau: $3123$ ✔, $34$, $35$, $37$, $310$ ⇒ chỉ có $3123$ chia hết cho 3 ⇒ in 1. Với $b_2 = 2$: $2123$, $24$ ✔, $25$, $27$ ✔, $210$ ✔ ⇒ in 3.

Nhắc lại ngưỡng TLE

Với giới hạn 1 giây, tổng số lần lặp của cả bài chỉ nên ở mức $(3 \div 5) \cdot 10^7$ là an toàn với phần lớn hệ thống chấm, cao lắm là $10^8$ (hên xui). Đó là với C/C++, còn Python, Java, C# chạy chậm hơn thì ngưỡng phải thấp hơn. Đề cho 2 giây thì nhân đôi ngưỡng, 100 ms thì chia 10, cứ thế mà tỷ lệ.

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Ghép số thật · O(N·M) · 60%Cách 2Tổng chữ số · O(N·M) · 60%Cách 3Đếm theo số dư · O(N + M) · 100%

Cách 1Làm đúng như đề: ghép số thật – O(N·M)

Cách dễ nhất nhưng chắc chắn không tối ưu là làm đúng như đề mô tả: với mỗi $b_i$, ghép lần lượt từng $a_j$ vào sau nó, kiểm tra số mới có chia hết cho 3 không, có thì tăng biến đếm. Xét hết các $a_j$ thì in kết quả, rồi chuyển sang $b_i$ tiếp theo và lại xét từ đầu dãy $a$. Cách này là vét cạn, không tối ưu, nhưng vẫn nên cài đặt để sau này lấy nó làm công cụ kiểm tra tính chính xác cho cách tối ưu.

Ta không cần tạo mảng $b$: mỗi $b_i$ chỉ dùng xong rồi bỏ, nên chỉ cần đọc vào một biến $x$ rồi xử lý luôn, không tốn bộ nhớ cho cả mảng $m$ phần tử.

Ghép số bằng công thức

Số mới $= b_i \times 10^{k} + a_j$, với $k$ là số chữ số của $a_j$. Ví dụ $123$ ghép với $45$: $123 \times 10^2 + 45 = 12300 + 45 = 12345$.

Coi chừng tràn số

$a_j, b_i \le 10^8$ thì int chứa vừa, nhưng số sau khi ghép có thể lên tới 18 chữ số ⇒ int không chứa nổi, phải dùng long long. Nếu vẫn để $b_i$ kiểu int thì ở bước tính $b_i \times 10^k$, trình biên dịch lưu kết quả tạm theo kiểu của các biến tham gia (tức int) ⇒ tràn ngay, nên phải ép kiểu. Trong code của mình, $x$ đã là long long và pow(10, cnt) được ép về long long nên không lo. Kết quả ghép lưu vào biến tạm temp2 để không làm thay đổi $x$, vì $x$ còn dùng để ghép với các $a_j$ tiếp theo.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, m;
    cin >> n >> m;
    int a[n];
    for(int i = 0; i < n; ++i){
        cin >> a[i];
    }
    while(m--){
        long long x;
        cin >> x;
        int res = 0;
        for(int j = 0; j < n; ++j){
            int temp = a[j];
            int cnt = 0;
            while(temp != 0){
                temp /= 10;
                cnt++;
            }
            long long temp2 = x * (long long)pow(10, cnt) + a[j];
            if(temp2 % 3 == 0){
                res++;
            }
        }
        cout << res << endl;
    }
    return 0;
}

import sys

data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
a = [int(v) for v in data[2:2 + n]]
out = []
for i in range(m):
    x = int(data[2 + n + i])
    res = 0
    for aj in a:
        temp = aj
        cnt = 0
        while temp != 0:
            temp //= 10
            cnt += 1
        temp2 = x * 10 ** cnt + aj  # ghép aj vào sau x
        if temp2 % 3 == 0:
            res += 1
    out.append(str(res))
print('\n'.join(out))

Đánh giá độ phức tạp của cách làm này:

• Không gian: mảng $a$ ⇒ $O(N)$.
• Thời gian: $O(N)$ đọc mảng $a$ + $O(M \cdot (N + \log a_j))$ cho phần xử lý chính (với mỗi cặp còn phải đếm chữ số của $a_j$). Trường hợp xấu nhất $N = M = 10^5$, $a_j$ có 8–9 chữ số ⇒ cỡ $10^5 \cdot 10^5 = 10^{10}$ lần lặp, tức hơn 10 tỷ lần, vượt xa ngưỡng $10^8$ ⇒ chắc chắn TLE, chỉ ăn được 60% số test có $n, m \le 1000$.

Không gian$O(N)$

Thời gian$O(N \cdot M)$

Cách 2Dấu hiệu chia hết cho 3: tổng các chữ số – O(N·M)

Hướng này độ phức tạp vẫn tương tự (vẫn chưa tối ưu), nhưng không cần mất công ghép số nữa. Dựa vào dấu hiệu quen thuộc: một số chia hết cho 3 khi và chỉ khi tổng các chữ số của nó chia hết cho 3. Số mới ghép $a_j$ sau $b_i$ có các chữ số chính là chữ số của $b_i$ rồi tới chữ số của $a_j$ ⇒ tổng chữ số của số mới = tổng chữ số của $b_i$ + tổng chữ số của $a_j$.

• Khi đọc mỗi $a_j$, tính luôn tổng các chữ số của nó và lưu đè vào $a_j$.
• Đọc từng $b_i$ vào biến $x$ (không cần mảng $b$), tính tổng chữ số sum của nó, rồi duyệt các $a_j$: nếu (sum + a[j]) % 3 == 0 thì ghép $a_j$ sau $x$ sẽ chia hết cho 3 ⇒ tăng biến đếm.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, m;
    cin >> n >> m;
    int a[n];
    for(int i = 0; i < n; ++i){
        cin >> a[i];
        int sum = 0;
        while(a[i] != 0){
            sum += a[i] % 10;
            a[i] /= 10;
        }
        a[i] = sum;
    }
    while(m--){
        int x;
        cin >> x;
        int sum = 0;
        while(x != 0){
            sum += x % 10;
            x /= 10;
        }
        int res = 0;
        for(int j = 0; j < n; ++j){
            if((sum + a[j]) % 3 == 0){
                res++;
            }
        }
        cout << res << endl;
    }
    return 0;
}

import sys

def tong_chu_so(v):
    s = 0
    while v != 0:
        s += v % 10
        v //= 10
    return s

data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
a = [tong_chu_so(int(v)) for v in data[2:2 + n]]  # a[i] = tổng chữ số của a[i]
out = []
for i in range(m):
    s = tong_chu_so(int(data[2 + n + i]))
    res = 0
    for aj in a:
        if (s + aj) % 3 == 0:
            res += 1
    out.append(str(res))
print('\n'.join(out))

Độ phức tạp cả về không gian hay thời gian vẫn tương tự cách 1: $O(N)$ bộ nhớ và $O(N \cdot M)$ thời gian ⇒ vẫn TLE với $N = M = 10^5$.

Không gian$O(N)$

Thời gian$O(N \cdot M)$

Cách 3Chỉ cần quan tâm số dư khi chia 3 – O(N + M)

Hai cách trên tuy đều ra kết quả đúng nhưng chẳng cách nào tối ưu cả. Cách tối ưu thực sự cho bài này đúng chất là tối ưu hơn hẳn cả về thời gian, bộ nhớ và thậm chí code còn ngắn gọn hơn rất nhiều, nếu các bạn nhìn ra được bản chất vấn đề hehe.

Như cách 2, gọi $x$ là tổng các chữ số của $a_j$, $y$ là tổng các chữ số của $b_i$. Cặp thoả mãn khi $(x + y) \bmod 3 = 0$. Phép chia dư cho 3 thì kết quả chỉ có thể là $0$, $1$ hoặc $2$, và ta có quy tắc modulo:

Quy tắc modulo

$(x + y) \bmod 3 = \big((x \bmod 3) + (y \bmod 3)\big) \bmod 3$

$x \bmod 3$	$y \bmod 3$ cần có	Kiểm tra
0	0	$(0 + 0) \bmod 3 = 0$
1	2	$(1 + 2) \bmod 3 = 0$
2	1	$(2 + 1) \bmod 3 = 0$

Nhìn sâu hơn nữa: số $14$ có tổng chữ số $1 + 4 = 5$, $5 \bmod 3 = 2$, và $14 \bmod 3$ cũng bằng $2$. Số $15$ có tổng $6$, $6 \bmod 3 = 0$, và $15 \bmod 3 = 0$. Số $16$ có tổng $7$, $7 \bmod 3 = 1$, và $16 \bmod 3 = 1$. Tức là một số và tổng các chữ số của nó luôn có cùng số dư khi chia cho 3 ⇒ ta chẳng cần tính tổng chữ số nữa, lấy luôn $a_j \bmod 3$ và $b_i \bmod 3$ là được!

Nhìn theo công thức ghép số

Số mới $= b_i \cdot 10^k + a_j$. Vì $10 \bmod 3 = 1$ nên $10^k \bmod 3 = 1$ ⇒ số mới $\bmod 3 = (b_i + a_j) \bmod 3$. Độ dài của $a_j$ hoàn toàn không ảnh hưởng gì cả 😁.

Đến đây đã quá rõ ràng, nhưng nếu xử lý không khéo thì vẫn sẽ phức tạp vấn đề. Sẽ rất đơn giản nếu ta dùng kỹ thuật mảng đánh dấu:

• Tạo mảng đếm a có 3 phần tử (chỉ số 0..2), khởi tạo toàn 0. Với mỗi giá trị $x$ đọc vào của dãy $a$ (lại chẳng cần lưu dãy $a$, chỉ dùng một biến đại diện $x$), tăng a[x % 3]++. Vậy a[r] là số lượng số trong dãy $a$ có số dư $r$ khi chia 3.
• Đọc lần lượt từng $b_i$ vào $x$ (cũng không cần mảng $b$): nếu $x \bmod 3 = 0$ thì đáp án là a[0]; nếu $x \bmod 3 = 1$ thì đáp án là a[2]; nếu $x \bmod 3 = 2$ thì đáp án là a[1].

Viết gọn bằng một công thức

cout << a[(3 - (x % 3)) % 3]; chính là cách viết gọn của:

if(x % 3 == 0) cout << a[0];
else if(x % 3 == 1) cout << a[2];
else cout << a[1];

Để hiểu thì cứ thế $x \bmod 3$ lần lượt là $0, 1, 2$: $(3 - 0) \bmod 3 = 0$, $(3 - 1) \bmod 3 = 2$, $(3 - 2) \bmod 3 = 1$. Đây cũng là chỗ để tối ưu code về mặt trình bày.

Minh hoạ

Em nhập dãy $a$, dãy $b$ rồi bấm Tiếp: mỗi số $a_j$ được "thả" vào một trong 3 giỏ theo số dư khi chia 3, sau đó mỗi $b_i$ chỉ việc nhìn vào đúng một giỏ để lấy đáp án:

Dãy a Dãy b

Ví dụ nhanh:

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, m, x;
    cin >> n >> m;
    int a[3] = {0};
    while(n--){
        cin >> x;
        a[x % 3]++;
    }
    while(m--){
        cin >> x;
        cout << a[(3 - (x % 3)) % 3] << endl;
    }
    return 0;
}

import sys

data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
a = [0, 0, 0]  # a[r] = số lượng số trong dãy a có số dư khi chia 3 là r
for i in range(n):
    a[int(data[2 + i]) % 3] += 1
out = []
for i in range(m):
    x = int(data[2 + n + i])
    out.append(str(a[(3 - x % 3) % 3]))
print('\n'.join(out))

C++▶ Chạy tay từng dòng codeĐếm số lượng a_j theo số dư chia 3, mỗi b_i tra đúng một ô.

Dữ liệu vào (stdin) – sửa thoải mái5 2 123 4 5 7 10 3 2

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4int main(){

5 int n, m, x;

6 cin >> n >> m;

7 int a[3] = {0};

8 while(n--){

9 cin >> x;

10 a[x % 3]++;

11 }

12 while(m--){

13 cin >> x;

14 cout << a[(3 - (x % 3)) % 3] << endl;

15 }

16 return 0;

17}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: mảng đánh dấu chỉ có 3 phần tử, chẳng đáng kể ⇒ $O(1)$.
• Thời gian: $O(N) + O(M)$, theo quy tắc cộng Big O lấy theo thằng lớn nhất ⇒ $O(\max(N, M))$. Trường hợp xấu nhất $N = M = 10^5$ chỉ lặp $2 \cdot 10^5$ lần, tức 200 ngàn lần ⇒ yên tâm không sợ TLE.

Không gian$O(1)$

Thời gian$O(N + M)$

Đến đây các bạn đã thấy cái hay của giải thuật rồi chứ? Từ hơn 10 tỷ lần lặp rút xuống chỉ còn 200 ngàn lần. Quá tuyệt vời đúng không các bạn 😍. Phải nặn óc ra suy nghĩ, nhưng chương trình chạy nhanh hơn rất nhiều, trong tình huống này còn tiết kiệm được bộ nhớ và rút ngắn số dòng code nữa, tối ưu đủ đường luôn rồi còn gì nữa 😁.

Ghi chú của mình: code C++ và Python của cả 3 cách đã được kiểm tra với 300 bộ test ngẫu nhiên nhỏ, so với code vét cạn ghép chuỗi trực tiếp – khớp hết. Với $n = m = 10^5$, $a_i, b_i$ ngẫu nhiên tới $10^8$: cách 3 chạy khoảng 0.1 giây (cả C++ lẫn Python); cách 2 (C++) mất hơn 10 giây và cách 1 (C++) chạy hơn 30 giây chưa xong ⇒ TLE đúng như phân tích, còn với $n = m = 1000$ thì cả hai đều chạy tức thì.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇