Ghép thẻ may mắn (Đề tự luyện HSG Tin 9 – Bài 1)

Nguồn: Đề tự luyện HSG Tin học 9 – Bài 1 (đề tự soạn)Độ khó: DễSố họcĐồng dưMảng tần suất

Đề bài

Ghép thẻ may mắn. Có $N$ tấm thẻ, thẻ $i$ ghi số nguyên dương $a_i$. Chọn hai thẻ khác nhau $i \ne j$, đặt thẻ $i$ bên trái, thẻ $j$ bên phải rồi đọc liền các chữ số (ví dụ $12$ và $345$ cho $12345$). Số ghép là số may mắn nếu chia hết cho $11$. Đếm số cặp có thứ tự $(i, j)$, $i \ne j$, cho ra số may mắn ($(i, j)$ và $(j, i)$ là hai cách khác nhau; hai thẻ khác nhau dù ghi cùng số vẫn tính riêng).

Dữ liệu vào: dòng 1 là $N$ $(1 \le N \le 2\cdot 10^5)$; dòng 2 là $a_1..a_N$ $(1 \le a_i \le 10^{18})$.

Kết quả: số cách chọn cặp $(i, j)$ cho ra số may mắn.

• Subtask 1 (20%): $N \le 1000$ và $a_i \le 10^8$.
• Subtask 2 (30%): $N \le 5000$.
• Subtask 3 (50%): không ràng buộc thêm.

Input

6
39 67 1946 39 9159 82

Output

6

Giải thích

Sáu cách: $39|82 = 3982$ (hai thẻ $39$ nên có hai cách), $82|39 = 8239$ (hai cách), $67|1946 = 671946$ và $1946|67 = 194667$. Cả bốn số này đều chia hết cho $11$.

Dành cho học viênNộp bài trên ClueOJ

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é. Bộ test có chia subtask và có cả những test "bẫy", nên code đúng ý tưởng nhưng sai chi tiết nhỏ cũng sẽ bị trừ điểm đó.

Nộp bài Ghép thẻ may mắn

Lời mở đầu

Bài toán nhìn rất "hiền": thử mọi cặp thẻ, ghép lại, kiểm tra chia hết cho $11$. Nhưng có hai chỗ làm cách ngây thơ đó gãy:

• Số ghép quá lớn. Mỗi thẻ có thể tới $19$ chữ số ($10^{18}$), ghép hai thẻ được số tới $38$ chữ số, vượt xa long long (khoảng $9{,}2\cdot 10^{18}$, tức 19 chữ số).
• Quá nhiều cặp. Với $N = 2\cdot 10^5$ có gần $4\cdot 10^{10}$ cặp, không thể thử hết trong 1 giây. Đáp án cũng có thể lớn tới cỡ đó, nên biến đếm phải là long long.

Chìa khóa của bài là nhìn phép "ghép" dưới dạng một phép tính số học: đặt $A$ bên trái $B$, mà $B$ có $L$ chữ số, thì giống như dịch $A$ sang trái $L$ chữ số rồi cộng $B$:

$$\overline{A\,B} = A \cdot 10^{L} + B.$$

Hình 1. Ghép thẻ là phép "nhân với $10^L$ rồi cộng", và $10^L$ chia $11$ chỉ có hai số dư xen kẽ: $10$ (khi $L$ lẻ) và $1$ (khi $L$ chẵn).

Ta không cần biết giá trị khổng lồ của số ghép, chỉ cần số dư khi chia cho 11. Mà số dư thì "đi qua" được phép cộng và phép nhân:

$$\overline{A\,B} \bmod 11 = \big((A \bmod 11)\cdot(10^{L} \bmod 11) + (B \bmod 11)\big) \bmod 11.$$

Mọi số trong vế phải đều nhỏ hơn $11$, không còn lo tràn số. Từ đây có ba cách làm, nhanh dần:

Cách 1Ghép trực tiếp · 20%Cách 2Thử mọi cặp bằng số dư · 50%Cách 3Đếm bằng mảng tần suất · 100%

Cách 1Ghép trực tiếp – O(N²) · 20%

Làm đúng như đề: với mỗi cặp $(i, j)$, $i \ne j$, tìm $pw = 10^{L}$ ($L$ là số chữ số của $a_j$) bằng cách nhân $10$ cho tới khi vượt $a_j$, rồi tính số ghép $a_i \cdot pw + a_j$ và kiểm tra chia hết cho $11$.

Ở Subtask 1, $a_i \le 10^8$ (tối đa 9 chữ số) nên số ghép nhỏ hơn $10^{8} \cdot 10^{9} + 10^8 < 10^{18}$, vừa đủ cho long long. Có $N^2 = 10^6$ cặp, chạy rất nhanh.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int n;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    ll ans = 0;
    for (int i = 0; i < n; i++)          // the trai
        for (int j = 0; j < n; j++) {    // the phai
            if (i == j) continue;
            ll pw = 1;                   // pw = 10^(so chu so cua a[j])
            while (pw <= a[j]) pw *= 10;
            ll so = a[i] * pw + a[j];    // ghep truc tiep (chi an toan khi a <= 10^8)
            if (so % 11 == 0) ans++;
        }
    cout << ans << '\n';
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a = [int(x) for x in data[1:n + 1]]
    ans = 0
    for i in range(n):                   # the trai
        for j in range(n):               # the phai
            if i == j:
                continue
            pw = 1                       # pw = 10^(so chu so cua a[j])
            while pw <= a[j]:
                pw *= 10
            so = a[i] * pw + a[j]        # ghep truc tiep
            if so % 11 == 0:
                ans += 1
    print(ans)

main()

Không gian$O(N)$

Thời gian$O(N^2 \cdot 19)$

Vì sao chỉ được 20%?

Ở Subtask 2 các thẻ có tới 19 chữ số: a[i] * pw tràn long long và cho số dư sai (bản C++ sai ở cả 10 test Subtask 2). Python không bị tràn số vì số nguyên của Python không giới hạn, nhưng phép tính trên số 38 chữ số chậm hơn nhiều, nên bản Python cũng không kịp thời gian.

Cách 2Thử mọi cặp bằng số dư – O(N²) · 50%

Dùng công thức số dư ở trên: chuẩn bị trước cho mỗi thẻ $i$ hai con số nhỏ

• $r_i = a_i \bmod 11$ (số dư của thẻ);
• $p_i = 10^{L_i} \bmod 11$, với $L_i$ là số chữ số của $a_i$ (tính bằng to_string(a[i]).size(), rồi nhân $10$ và lấy dư $L_i$ lần).

Thẻ $i$ bên trái, thẻ $j$ bên phải cho số may mắn khi và chỉ khi $(r_i \cdot p_j + r_j) \bmod 11 = 0$. Mọi phép tính đều trên số nhỏ hơn $121$, không thể tràn. Với $N = 5000$ có $2{,}5\cdot 10^7$ cặp — vẫn nhanh.

Ví dụ với thẻ trái $67$ và thẻ phải $1946$: $r = 67 \bmod 11 = 1$, thẻ phải có $4$ chữ số nên $p = 10^4 \bmod 11 = 1$, và $1946 \bmod 11 = 10$. Ta được $(1 \cdot 1 + 10) \bmod 11 = 0$: số $671946$ chia hết cho $11$ mà không cần tính ra nó.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int n;
    cin >> n;
    vector<ll> a(n);
    vector<int> r(n), p(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        r[i] = a[i] % 11;                // du cua a[i] khi chia 11
        int len = to_string(a[i]).size();
        p[i] = 1;
        for (int t = 0; t < len; t++) p[i] = p[i] * 10 % 11;   // 10^len mod 11
    }
    ll ans = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (i != j && (r[i] * p[j] + r[j]) % 11 == 0) ans++;
    cout << ans << '\n';
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    toks = data[1:n + 1]
    r = [int(x) % 11 for x in toks]          # du cua a[i] khi chia 11
    p = [pow(10, len(x), 11) for x in toks]  # 10^len mod 11
    ans = 0
    for i in range(n):
        ri = r[i]
        for j in range(n):
            if i != j and (ri * p[j] + r[j]) % 11 == 0:
                ans += 1
    print(ans)

main()

Không gian$O(N)$

Thời gian$O(N^2)$

Đừng tính số chữ số bằng log10

Cách "nhanh gọn" len = (int)log10((double)a) + 1 sai với những số như $999999999999999$ (15 chữ số 9): kiểu double không đủ chính xác, log10 trả về đúng $15$ nên ra $16$ chữ số. Sai số chữ số là sai luôn $10^L \bmod 11$! Bộ test có rải những số dạng $99\ldots9$ dài 15–18 chữ số để bắt lỗi này. Hãy dùng to_string(a).size() hoặc vòng lặp chia $10$.

Cách 3Đếm bằng mảng tần suất – O(11·N) · 100%

Ở Cách 2, khi đã cố định thẻ phải $j$ thì điều kiện $(r_i \cdot p_j + r_j) \bmod 11 = 0$ chỉ phụ thuộc vào số dư $r_i$ của thẻ trái, không cần biết thẻ trái cụ thể là thẻ nào. Mà số dư chỉ có $11$ giá trị $0, 1, \dots, 10$! Vậy ta đếm trước:

$$cnt[r] = \text{số thẻ có } a_i \bmod 11 = r \qquad (r = 0, 1, \dots, 10).$$

Rồi với mỗi thẻ phải $j$, ta thử $11$ số dư $r$ của thẻ trái: số dư nào thỏa $(r \cdot p_j + r_j) \bmod 11 = 0$ thì cộng $cnt[r]$ vào đáp án. Còn một chi tiết: $cnt[r]$ đếm mọi thẻ, kể cả chính thẻ $j$. Nếu thẻ $j$ ghép với chính nó cũng thỏa điều kiện thì ta đã đếm thừa cặp $(j, j)$, phải trừ đi $1$.

Thẻ ghép với chính nó

Thẻ có số chữ số lẻ luôn ghép với chính nó ra số chia hết cho $11$: $7 \to 77$, $123 \to 123123 = 11 \cdot 11193$. Lý do: $p = 10$ nên $r \cdot 10 + r = 11r$. Quên trừ cặp $(j, j)$ là mất gần trọn bài: bộ test chỉ có đúng một test không bắt được lỗi này.

Chạy tay ví dụ của đề

Các thẻ trong ví dụ đều có $2$ hoặc $4$ chữ số nên $p_j = 1$ với mọi $j$, điều kiện trở thành $(r + r_j) \bmod 11 = 0$.

Thẻ j (bên phải)	aj	rj = aj mod 11	pj	r cần ở thẻ trái	cnt[r]	trừ (j, j)?	cộng thêm
1	39	6	1	5	1	không	1
2	67	1	1	10	1	không	1
3	1946	10	1	1	1	không	1
4	39	6	1	5	1	không	1
5	9159	7	1	4	0	không	0
6	82	5	1	6	2	không	2

Mảng đếm: $cnt[1] = 1$ (thẻ 67), $cnt[5] = 1$ (thẻ 82), $cnt[6] = 2$ (hai thẻ 39), $cnt[7] = 1$, $cnt[10] = 1$. Tổng cộng $1+1+1+1+0+2 = 6$, đúng đáp án. Hàng cuối: thẻ phải $82$ ghép được với hai thẻ trái cùng ghi $39$, mảng đếm cộng một lần là đủ cả hai.

Mô phỏng dưới đây cho các bạn tự nhập dãy thẻ (tối đa 10 thẻ) và xem từng bước đếm.

Các thẻ a

Ví dụ nhanh:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<ll> a(n);
    ll cnt[11] = {0};                    // cnt[r] = so the co a[i] chia 11 du r
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        cnt[a[i] % 11]++;
    }
    ll ans = 0;
    for (int j = 0; j < n; j++) {        // the j dat ben PHAI
        int len = to_string(a[j]).size();  // so chu so cua a[j]
        int y = a[j] % 11;
        int p = 1;
        for (int t = 0; t < len; t++) p = p * 10 % 11;   // p = 10^len mod 11
        // so ghep = a[i] * 10^len + a[j]  ->  du (r * p + y) mod 11
        for (int r = 0; r < 11; r++)
            if ((r * p + y) % 11 == 0) ans += cnt[r];
        if ((y * p + y) % 11 == 0) ans--;  // bo cach chon i = j
    }
    cout << ans << '\n';
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    toks = data[1:n + 1]
    vals = [int(x) % 11 for x in toks]
    cnt = [0] * 11                      # cnt[r] = so the co a[i] chia 11 du r
    for y in vals:
        cnt[y] += 1
    # p[len] = 10^len mod 11
    p = [1] * 21
    for L in range(1, 21):
        p[L] = p[L - 1] * 10 % 11
    # good[p][y] = so the ben TRAI ghep voi the phai (du y, p) cho so chia het cho 11
    good = {}
    for pp in (1, 10):
        g = []
        for y in range(11):
            s = 0
            for r in range(11):
                if (r * pp + y) % 11 == 0:
                    s += cnt[r]
            if (y * pp + y) % 11 == 0:
                s -= 1                  # bo cach chon i = j
            g.append(s)
        good[pp] = g
    ans = 0
    for j in range(n):                  # the j dat ben PHAI
        ans += good[p[len(toks[j])]][vals[j]]
    print(ans)

main()

Không gian$O(N)$

Thời gian$O(N \cdot (11 + 19))$

Về bản Python

Bản Python dùng luôn độ dài của chuỗi byte đọc vào làm số chữ số (len(toks[j])), và vì $p_j$ chỉ có hai giá trị $1$ hoặc $10$ nên tính sẵn "số thẻ trái hợp lệ" cho mỗi cặp $(p, r_j)$, tổng cộng chỉ $2 \times 11$ ô. Ý tưởng giống hệt bản C++.

C++▶ Chạy tay từng dòng codeĐếm cnt[r], rồi với mỗi thẻ phải j thử 11 số dư của thẻ trái.

Dữ liệu vào (stdin) – sửa thoải mái6 39 67 1946 39 9159 82

Dữ liệu mẫu:

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

2using namespace std;

3typedef long long ll;

4int main() {

5 ios::sync_with_stdio(false);

6 cin.tie(nullptr);

7 int n;

8 cin >> n;

9 vector<ll> a(n);

10 ll cnt[11] = {0}; // cnt[r] = so the co a[i] chia 11 du r

11 for (int i = 0; i < n; i++) {

12 cin >> a[i];

13 cnt[a[i] % 11]++;

14 }

15 ll ans = 0;

16 for (int j = 0; j < n; j++) { // the j dat ben PHAI

17 int len = to_string(a[j]).size(); // so chu so cua a[j]

18 int y = a[j] % 11;

19 int p = 1;

20 for (int t = 0; t < len; t++) p = p * 10 % 11; // p = 10^len mod 11

21 // so ghep = a[i] * 10^len + a[j] -> du (r * p + y) mod 11

22 for (int r = 0; r < 11; r++)

23 if ((r * p + y) % 11 == 0) ans += cnt[r];

24 if ((y * p + y) % 11 == 0) ans--; // bo cach chon i = j

25 }

26 cout << ans << '\n';

27 return 0;

28}

ChậmVừaNhanhRất nhanh

Bộ test chấm "bắt" những lỗi nào?

Bộ test có 32 test: Subtask 1 có 10 test ($N \le 1000$, $a_i \le 10^8$; gồm ví dụ, $N = 1$, hai thẻ $5\ 5$, $1000$ thẻ đều là $10^8$...), Subtask 2 có 10 test ($N \approx 5000$, thẻ tới $19$ chữ số, có cả $10^{18}$), Subtask 3 có 12 test ($N \approx 2\cdot 10^5$, đáp án cỡ $3{,}6\cdot 10^9$ tới $4\cdot 10^{10}$). Các kiểu dãy: độ dài ngẫu nhiên, toàn số chữ số lẻ, toàn số chữ số chẵn, nhiều bội của $11$, nhiều thẻ trùng nhau, và rải các số dạng $99\ldots9$ dài 15–18 chữ số. Điểm tính theo từng test (thang 100%).

Cách làm	Sub 1 (10 test)	Sub 2 (10 test)	Sub 3 (12 test)	Điểm
Cách 1 – Ghép trực tiếp bằng long long	Đúng 10/10	WA 0/10 (tràn số)	TLE 0/12	20
Cách 2 – Thử mọi cặp bằng số dư, $O(N^2)$	Đúng 10/10	Đúng 10/10	TLE 0/12	50
Cách 3 – Mảng tần suất, $O(11N)$ (chuẩn)	Đúng 10/10	Đúng 10/10	Đúng 12/12	100
Sai: quên trừ cặp $(j, j)$	WA 1/10	WA 0/10	WA 0/12	2
Sai: đếm cặp không thứ tự ($i < j$)	WA 1/10	WA 0/10	WA 0/12	2
Sai: chỉ xét $(a_i + a_j)$ chia hết cho $11$	WA 2/10	WA 1/10	WA 1/12	11,2
Sai: biến đếm int	Đúng 10/10	Đúng 10/10	WA 0/12	50
Sai: số chữ số tính bằng log10	Đúng 10/10	WA 5/10	WA 6/12	60

Ghi chú của mình: các cách C++ ở trên đã được chấm thử với đúng bộ test của bài: Cách 1 đúng 10/10 test Subtask 1, sai cả 10 test Subtask 2 vì tràn long long và quá thời gian (hơn 3 giây) ở cả 12 test Subtask 3; Cách 2 đúng 20/20 test của hai subtask đầu và quá thời gian ở cả 12 test Subtask 3; Cách 3 đúng 32/32 test, test lâu nhất chạy khoảng 0,05 giây. Lời giải Python của Cách 3 cũng đúng 32/32 test, chạy tối đa khoảng 0,1 giây với CPython. Ví dụ của đề toàn thẻ có số chữ số chẵn và không thẻ nào ghép với chính nó ra số may mắn, nên ba lỗi "quên trừ $(j, j)$", "chỉ xét tổng" và "dùng log10" đều vẫn ra đúng $6$ — qua ví dụ chưa chắc đã đúng nha!

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 😇