Quỹ khuyến học (Đề tự luyện HSG Tin 9 – Bài 1) – Xử lý xâu chữ số, dấu hiệu chia hết cho 3 và 4, đếm giá trị khác nhau

Nguồn: Đề tự luyện HSG Tin học 9 – Bài 1 (đề tự soạn)Độ khó: DễXử lý xâuDấu hiệu chia hếtĐếm giá trị khác nhau

Đề bài

Quỹ khuyến học. Tổng quỹ thật $T$ là một số nguyên dương chia hết cho $12$ (góp đều trong $12$ tháng). Bạn thư ký chép vào sổ thì viết thừa đúng một chữ số, được xâu $S$ gồm $n$ chữ số. Nói cách khác, $T$ là số nhận được khi xoá đúng một chữ số của $S$, sao cho chữ số đầu của $T$ khác $0$ và $T$ chia hết cho $12$. Đếm số giá trị khác nhau mà $T$ có thể nhận.

Dữ liệu vào: một dòng chứa xâu $S$ $(2 \le n \le 10^6)$; $S$ có thể bắt đầu bằng chữ số $0$.

Kết quả: số giá trị khác nhau của $T$ (có thể bằng $0$).

• Subtask 1 (40%): $n \le 18$.
• Subtask 2 (30%): $n \le 5000$.
• Subtask 3 (30%): không ràng buộc thêm.

Input

25484000

Output

3

Giải thích

Xoá chữ số $2$: $5484000 = 12 \cdot 457000$; xoá chữ số $5$: $2484000 = 12 \cdot 207000$; xoá chữ số $8$: $2544000 = 12 \cdot 212000$. Xoá một trong hai chữ số $4$ hay một trong ba chữ số $0$ cuối đều ra số không chia hết cho $12$ ($2584000$, $2548000$, $2548400$).

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 Quỹ khuyến học

Lời mở đầu

Đề bài nghe thì đơn giản: thử xoá từng chữ số một, xem số còn lại có chia hết cho $12$ không, rồi đếm. Nhưng có ba chỗ rất dễ "trượt chân":

1. "Giá trị khác nhau" chứ không phải "cách xoá khác nhau". Nếu có hai chữ số giống nhau đứng liền nhau, xoá chữ số nào trong hai chữ số đó cũng ra cùng một số. Ví dụ $S = 1\,2\,2\,4\,0$: xoá chữ số $2$ thứ nhất hay thứ hai đều được $1240$. Ngược lại, xoá ở hai "khối" chữ số khác nhau thì luôn ra hai số khác nhau (so hai số đó từ trái sang, chỗ khác nhau đầu tiên nằm ở đoạn giữa hai vị trí xoá). Vậy: mỗi khối các chữ số giống nhau liền nhau chỉ tính một lần.
2. Chữ số $0$ ở đầu. $T$ là cách viết bình thường của một số, nên chữ số đầu phải khác $0$. Chữ số đầu của $T$ là $S[0]$, trừ khi ta xoá chính $S[0]$ — khi đó chữ số đầu là $S[1]$.
3. Số rất dài. $n$ tới $10^6$ chữ số: không kiểu số nguyên nào chứa nổi, phải làm việc trên các chữ số.

Hình 1. Xoá chữ số nào trong cùng một khối chữ số giống nhau liền nhau cũng ra cùng một số.

Còn việc kiểm tra "chia hết cho $12$" thì có hai hướng: tính số dư khi chia cho $12$ theo từng chữ số (Cách 2), hoặc dùng dấu hiệu chia hết (Cách 3). Lộ trình:

Cách 1Dựng T bằng long long · 40%Cách 2Số dư theo từng chữ số · 70%Cách 3Dấu hiệu chia hết cho 3 và 4 · 100%

Cách 1Dựng T thành số long long – O(n²) · 40%

Với $n \le 18$ thì $T$ có tối đa $17$ chữ số, vừa kiểu long long (tới khoảng $9{,}2 \cdot 10^{18}$). Ta thử xoá từng vị trí $i$: tạo xâu $t$ bằng s.substr(0, i) + s.substr(i + 1), bỏ qua nếu t[0] == '0', đổi $t$ ra số rồi kiểm tra T % 12 == 0. Các giá trị hợp lệ cho vào một mảng, sắp xếp rồi bỏ trùng bằng unique (Python thì dùng set) — như vậy không cần nghĩ tới chuyện "khối chữ số giống nhau".

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s;
    cin >> s;
    int n = s.size();
    vector<long long> ds;                      // cac gia tri T hop le (co the trung nhau)
    for (int i = 0; i < n; i++) {
        string t = s.substr(0, i) + s.substr(i + 1);   // xoa chu so thu i
        if (t[0] == '0') continue;             // co so 0 vo nghia o dau
        long long T = 0;
        for (char c : t) T = T * 10 + (c - '0');       // n <= 18 nen T vua long long
        if (T % 12 == 0) ds.push_back(T);
    }
    sort(ds.begin(), ds.end());
    int dem = unique(ds.begin(), ds.end()) - ds.begin();   // bo cac gia tri trung
    cout << dem << "\n";
    return 0;
}

s = input().strip()
n = len(s)
ds = set()                                   # cac gia tri T hop le, set tu bo trung
for i in range(n):
    t = s[:i] + s[i + 1:]                    # xoa chu so thu i
    if t[0] == '0':
        continue                             # co so 0 vo nghia o dau
    T = int(t)
    if T % 12 == 0:
        ds.add(T)
print(len(ds))

Không gian$O(n)$

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

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

Khi $n \ge 20$, phép T = T * 10 + ... bị tràn số: kết quả sai mà chương trình không báo gì. Với Subtask 3 ($n = 10^6$) thì việc tạo $n$ xâu dài $n$ còn quá thời gian. (Python không bị tràn số nhưng đổi xâu $10^6$ chữ số ra số nguyên $10^6$ lần thì cũng quá chậm.)

Cách 2Tính số dư theo từng chữ số – O(n²) · 70%

Muốn biết $T$ có chia hết cho $12$ không, ta chỉ cần số dư của $T$ khi chia cho $12$, và số dư này tính được khi đọc lần lượt từng chữ số (như khi chia tay một số lớn): bắt đầu du = 0, gặp chữ số $c$ thì du = (du * 10 + c) % 12. Biến du luôn nhỏ hơn $12$ nên không bao giờ tràn số.

Để khỏi lưu các xâu, ta bỏ trùng ngay theo nhận xét ở Lời mở đầu: bỏ qua vị trí $i$ nếu $S[i] = S[i+1]$ (chỉ xét vị trí cuối của mỗi khối). Chữ số đầu của $T$ là s[1] khi $i = 0$, ngược lại là s[0].

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s;
    cin >> s;
    int n = s.size();
    int dem = 0;
    for (int i = 0; i < n; i++) {
        if (i + 1 < n && s[i] == s[i + 1]) continue;    // xoa s[i] hay s[i+1] deu ra cung mot so
        if ((i == 0 ? s[1] : s[0]) == '0') continue;    // T co so 0 vo nghia o dau
        int du = 0;                                     // T mod 12, tinh lan luot tung chu so
        for (int j = 0; j < n; j++)
            if (j != i) du = (du * 10 + (s[j] - '0')) % 12;
        if (du == 0) dem++;
    }
    cout << dem << "\n";
    return 0;
}

import sys

def main():
    s = sys.stdin.readline().strip()
    n = len(s)
    d = [ord(c) - 48 for c in s]
    dem = 0
    for i in range(n):
        if i + 1 < n and s[i] == s[i + 1]:
            continue                         # xoa s[i] hay s[i+1] deu ra cung mot so
        if (s[1] if i == 0 else s[0]) == '0':
            continue                         # T co so 0 vo nghia o dau
        du = 0                               # T mod 12, tinh lan luot tung chu so
        for j in range(n):
            if j != i:
                du = (du * 10 + d[j]) % 12
        if du == 0:
            dem += 1
    print(dem)

main()

Không gian$O(n)$

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

Với $n \le 5000$ là khoảng $2{,}5 \cdot 10^7$ phép tính: ổn. Nhưng $n = 10^6$ thì là $10^{12}$ phép — quá thời gian. Ta cần kiểm tra mỗi cách xoá trong $O(1)$.

Cách 3Dấu hiệu chia hết cho 3 và cho 4 – O(n) · 100%

Vì $12 = 3 \times 4$ và $3$, $4$ nguyên tố cùng nhau, nên

$T \;\vdots\; 12 \iff T \;\vdots\; 3$ và $T \;\vdots\; 4$.

• Chia hết cho 3: tổng các chữ số chia hết cho $3$. Tổng chữ số của $T$ = (tổng chữ số của $S$) − (chữ số bị xoá). Tính tổng của $S$ một lần, mỗi cách xoá kiểm tra trong $O(1)$.
• Chia hết cho 4: số tạo bởi hai chữ số cuối chia hết cho $4$ (vì $100$ chia hết cho $4$). Hai chữ số cuối của $T$ chỉ có ba khả năng:
  • xoá ở vị trí $i \le n - 3$: vẫn là $S[n-2]\,S[n-1]$;
  • xoá $S[n-2]$: thành $S[n-3]\,S[n-1]$;
  • xoá $S[n-1]$: thành $S[n-3]\,S[n-2]$.
  Riêng $n = 2$ thì $T$ chỉ có một chữ số (khi đó $T \le 9$ nên không bao giờ chia hết cho $12$, nhưng code vẫn xử lý gọn).

Bẫy: "chia hết cho 2 và cho 6"

Nhiều bạn nhớ nhầm "$12 = 2 \times 6$ nên chia hết cho $2$ và $6$ là chia hết cho $12$". Sai! Vì $2$ và $6$ không nguyên tố cùng nhau: số $30$ chia hết cho cả $2$ và $6$ nhưng không chia hết cho $12$. Phải tách thành $3 \times 4$.

Mô phỏng dưới đây chạy đúng các bước trên: tô màu từng khối chữ số, rồi với mỗi khối kiểm tra chữ số đầu, tổng chữ số và hai chữ số cuối của $T$.

Xâu S

Ví dụ nhanh:

Code hoàn chỉnh: một vòng tính tổng chữ số, một vòng xét từng vị trí, mỗi vị trí làm $O(1)$ việc.

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    int n = s.size();
    int tong = 0;                                       // tong cac chu so cua S
    for (int i = 0; i < n; i++) tong += s[i] - '0';
    int dem = 0;
    for (int i = 0; i < n; i++) {
        if (i + 1 < n && s[i] == s[i + 1]) continue;    // xoa s[i] hay s[i+1] deu ra cung mot so
        char dau = (i == 0) ? s[1] : s[0];              // chu so dau tien cua T
        if (dau == '0') continue;                       // T khong duoc co so 0 o dau
        if ((tong - (s[i] - '0')) % 3 != 0) continue;   // T chia het cho 3
        int hai;                                        // so tao boi hai chu so cuoi cua T
        if (n == 2) hai = s[1 - i] - '0';               // T chi co mot chu so
        else if (i <= n - 3) hai = (s[n - 2] - '0') * 10 + (s[n - 1] - '0');
        else if (i == n - 2) hai = (s[n - 3] - '0') * 10 + (s[n - 1] - '0');
        else hai = (s[n - 3] - '0') * 10 + (s[n - 2] - '0');
        if (hai % 4 == 0) dem++;                        // T chia het cho 4
    }
    cout << dem << "\n";
    return 0;
}

import sys

def main():
    s = sys.stdin.readline().strip()
    n = len(s)
    d = [ord(c) - 48 for c in s]
    tong = sum(d)                                   # tong cac chu so cua S
    dem = 0
    for i in range(n):
        if i + 1 < n and s[i] == s[i + 1]:
            continue                                # xoa s[i] hay s[i+1] deu ra cung mot so
        dau = s[1] if i == 0 else s[0]              # chu so dau tien cua T
        if dau == '0':
            continue                                # T khong duoc co so 0 o dau
        if (tong - d[i]) % 3 != 0:
            continue                                # T chia het cho 3
        if n == 2:
            hai = d[1 - i]                          # T chi co mot chu so
        elif i <= n - 3:
            hai = d[n - 2] * 10 + d[n - 1]
        elif i == n - 2:
            hai = d[n - 3] * 10 + d[n - 1]
        else:
            hai = d[n - 3] * 10 + d[n - 2]
        if hai % 4 == 0:
            dem += 1                                # T chia het cho 4
    print(dem)

main()

Không gian$O(n)$

Thời gian$O(n)$

C++▶ Chạy tay từng dòng codeTính tổng chữ số, rồi với mỗi khối kiểm tra chữ số đầu, chia hết cho 3 và hai chữ số cuối.

Dữ liệu vào (stdin) – sửa thoải mái25484000

Dữ liệu mẫu:

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

2using namespace std;

3int main() {

4 ios::sync_with_stdio(false);

5 cin.tie(nullptr);

6 string s;

7 cin >> s;

8 int n = s.size();

9 int tong = 0; // tong cac chu so cua S

10 for (int i = 0; i < n; i++) tong += s[i] - '0';

11 int dem = 0;

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

13 if (i + 1 < n && s[i] == s[i + 1]) continue; // xoa s[i] hay s[i+1] deu ra cung mot so

14 char dau = (i == 0) ? s[1] : s[0]; // chu so dau tien cua T

15 if (dau == '0') continue; // T khong duoc co so 0 o dau

16 if ((tong - (s[i] - '0')) % 3 != 0) continue; // T chia het cho 3

17 int hai; // so tao boi hai chu so cuoi cua T

18 if (n == 2) hai = s[1 - i] - '0'; // T chi co mot chu so

19 else if (i <= n - 3) hai = (s[n - 2] - '0') * 10 + (s[n - 1] - '0');

20 else if (i == n - 2) hai = (s[n - 3] - '0') * 10 + (s[n - 1] - '0');

21 else hai = (s[n - 3] - '0') * 10 + (s[n - 2] - '0');

22 if (hai % 4 == 0) dem++; // T chia het cho 4

23 }

24 cout << dem << "\n";

25 return 0;

26}

ChậmVừaNhanhRất nhanh

Nếu số chia không phải 12 thì sao?

Với số chia $K$ bất kỳ, ta vẫn làm được $O(n)$: tính trước số dư của mọi tiền tố $S[0..i-1]$ và mọi hậu tố $S[i+1..n-1]$ khi chia cho $K$, cùng với $10^j \bmod K$; khi đó $T \bmod K = (\text{tiền tố} \cdot 10^{n-1-i} + \text{hậu tố}) \bmod K$. Các em thử tự viết xem nhé (nhớ dùng long long khi nhân).

Những cái bẫy hay gặp

(1) Đếm theo vị trí xoá chứ không theo giá trị: khối "000" bị đếm 3 lần. (2) Quên điều kiện chữ số $0$ ở đầu (ví dụ $S = 4012$: xoá $4$ được "$012$" — không phải cách viết hợp lệ). (3) Luôn lấy hai chữ số cuối của $S$, quên rằng xoá một trong hai chữ số cuối làm đuôi thay đổi. (4) "Chia hết cho 2 và 6" thay cho "chia hết cho 3 và 4". Ví dụ của đề cho cả bốn lỗi này ra đúng 3!

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

Bộ test có 29 test: Subtask 1 có 10 test ($n \le 18$: ví dụ, $n = 2$, $S$ bắt đầu bằng $0$, một khối $0$ rất dài, "$4012$", …), Subtask 2 có 9 test ($n \approx 5000$), Subtask 3 có 10 test ($n \approx 10^6$). Các kiểu dữ liệu: ngẫu nhiên; nhiều khối chữ số lặp (bắt lỗi đếm theo vị trí); $S[1] = 0$ và xoá $S[0]$ ra số chia hết cho $12$ (bắt lỗi quên số $0$ ở đầu); ba chữ số cuối được chọn để xoá ở cuối làm đổi đuôi; đuôi chia $4$ dư $2$ (bắt lỗi "2 và 6"); rất nhiều chữ số $0$. Điểm tính theo từng test (thang 100%).

Cách làm	Sub 1 (10 test)	Sub 2 (9 test)	Sub 3 (10 test)	Điểm
Cách 1 – Dựng T bằng long long	Đúng 10/10	WA 0/9	TLE 0/10	40
Cách 2 – Số dư theo từng chữ số	Đúng 10/10	Đúng 9/9	TLE 0/10	70
Cách 3 – Dấu hiệu chia hết (chuẩn)	Đúng 10/10	Đúng 9/9	Đúng 10/10	100
Sai: đếm theo vị trí xoá (không bỏ trùng)	Đúng 10/10	WA 1/9	WA 1/10	46,3
Sai: quên điều kiện chữ số 0 ở đầu	WA 6/10	WA 8/9	WA 7/10	71,7
Sai: luôn lấy hai chữ số cuối của S	WA 5/10	WA 7/9	WA 7/10	64,3
Sai: "chia hết cho 2 và 6"	WA 7/10	WA 8/9	WA 7/10	75,7

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ả 9 test Subtask 2 (tràn long long) và quá thời gian (hơn 3 giây) cả 10 test Subtask 3; Cách 2 đúng 19/19 test của hai subtask đầu và quá thời gian cả 10 test Subtask 3; Cách 3 đúng 29/29 test, test lâu nhất chạy khoảng 0,01 giây. Lời giải Python của Cách 3 cũng đúng 29/29 test, chạy tối đa khoảng 0,3 giây với CPython. Ví dụ của đề khá "hiền": khối chữ số lặp duy nhất là "000" mà xoá vào cũng không hợp lệ, không có số $0$ ở đầu, hai chữ số cuối luôn là $00$ — nên cả bốn lời giải sai ở bảng trên đều vẫn ra đúng 3. Nhớ tự nghĩ thêm test 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 😇