Chia hết (Tin học trẻ toàn quốc 2025 – Vòng chung kết toàn quốc – Bảng B)
Đề bài
Cho số tự nhiên $a$ và số nguyên dương $m$. Em được xoá đi một số chữ số bất kỳ trong cách viết thập phân của $a$ (cũng có thể không xoá chữ số nào), các chữ số còn lại giữ nguyên thứ tự và tạo thành số $b$ (phải còn lại ít nhất một chữ số; nếu $b$ có các số 0 ở đầu thì hiểu theo giá trị, ví dụ 05 là $5$).
Hãy tìm số $b$ lớn nhất tạo được mà $b$ chia hết cho $m$. Nếu không có cách nào thì in ra dấu chấm than !.
Dữ liệu vào:
- Dòng đầu là số bộ dữ liệu $T$ $(1 \le T \le 10)$.
- Mỗi bộ dữ liệu là một dòng gồm hai số $a$ và $m$ $(0 \le a \le 10^{1000},\ 1 \le m \le 1000)$.
Kết quả: với mỗi bộ dữ liệu in trên một dòng số $b$ lớn nhất (viết không có số 0 thừa ở đầu), hoặc ! nếu không tồn tại.
Subtask:
- Subtask 1 ($30\%$ số điểm): $a \le 10^{18}$.
- Subtask 2 ($30\%$ số điểm): $a \le 10^{100}$.
- Subtask 3 ($40\%$ số điểm): không có ràng buộc gì thêm.
Giới hạn thời gian: 0,5 giây. Dữ liệu nhập từ bàn phím, in ra màn hình.
6
982025 81
13570 100
11111111 2
123456789 9
10001389 139
9876543210123456789 112025
0
!
123456789
10008
987654321123456789Giải thích:
- $982025$, $m = 81$: giữ lại $2025 = 81 \cdot 25$.
- $13570$, $m = 100$: chỉ có thể giữ lại một chữ số $0$, và $0$ chia hết cho $100$.
- $11111111$, $m = 2$: mọi số tạo được đều lẻ nên không chia hết cho 2 →
!. - $123456789$, $m = 9$: tổng các chữ số là 45 nên giữ nguyên cả số.
- $10001389$, $m = 139$: giữ lại $10008 = 139 \cdot 72$.
Lời mở đầu
Đây là bài "phân loại" của bảng B vòng chung kết. Với $a \le 10^{18}$ ta chỉ cần thử mọi cách xoá. Nhưng $a$ có tới 1000 chữ số thì số cách xoá là $2^{1000}$, còn đáp án thì không vừa bất kỳ kiểu số nguyên nào. Mình sẽ đi qua 3 cách: vét cạn → quy hoạch động theo số dư, lưu luôn cả con số → quy hoạch động chỉ lưu độ dài rồi tham lam dựng đáp án. Cách cuối cùng là một kỹ thuật rất hay gặp: "tìm đáp án tốt nhất theo thứ tự từ điển = QHĐ tính khả năng + tham lam từng vị trí".
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 OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test có gì?
Bộ test trên CLUE gồm 25 test (mình tự sinh theo đúng ràng buộc và tỉ lệ subtask của đề), mỗi test có tới 10 bộ dữ liệu:
| Nhóm | Test | Số bộ | Số chữ số của $a$ | $m$ | Số bộ in ! | Số bộ in 0 | Đáp án dài nhất |
|---|---|---|---|---|---|---|---|
| Subtask 1 (30%) | 2–8 | 70 | 1 – 19 | 1 – 1000 | 24 | 10 | 19 |
| Subtask 2 (30%) | 1, 9–16 | 86 | 5 – 101 | 1 – 1000 | 19 | 2 | 101 |
| Subtask 3 (40%) | 17–25 | 90 | 9 – 1001 | 1 – 1000 | 25 | 3 | 1001 |
- Test 1 chính là ví dụ của đề; vì có số $9876543210123456789 > 10^{18}$ nên mình xếp nó vào subtask 2.
- Có đủ các trường hợp đặc biệt: $a = 0$, $m = 1$ (giữ nguyên cả số), đáp án chỉ là
0, không có đáp án (!), $a$ chỉ gồm 0 và 1, $m = 1000$ (cần 3 chữ số 0 ở cuối)... - Đáp án ở subtask 3 dài tới cả nghìn chữ số – không thể lưu bằng kiểu số nguyên, phải dựng dưới dạng xâu.
Kết quả chạy thật của 3 cách (C++, giới hạn 0,5 giây) theo từng subtask:
| Subtask | Điều kiện | Test | Cách 1 vét cạn | Cách 2 QHĐ giữ cả số | Cách 3 QHĐ độ dài + tham lam |
|---|---|---|---|---|---|
| Subtask 1 (30%) | $a \le 10^{18}$ | 2–8 | qua | qua | qua |
| Subtask 2 (30%) | $a \le 10^{100}$ | 1, 9–16 | 1/9 test | qua | qua |
| Subtask 3 (40%) | $a \le 10^{1000}$ | 17–25 | quá thời gian | 3/9 test | qua |
Lời giải cách 3 (C++) mình đã nộp thử trên hệ thống chấm chính thức của hội thi (tinhoctre.vn) và đạt AC 100/100 điểm.
Ý tưởngDài hơn là lớn hơn
Trước hết tách riêng trường hợp đặc biệt: nếu đáp án là $0$ thì chỉ cần giữ lại một chữ số 0. Còn đáp án khác 0 thì ta luôn có thể coi nó bắt đầu bằng một chữ số khác 0 (các số 0 ở đầu xoá đi cũng không làm đổi giá trị). Với các số không có số 0 ở đầu:
Vậy ta muốn: (1) đáp án dài nhất có thể, (2) trong các đáp án dài nhất, chọn chữ số đầu lớn nhất, rồi chữ số thứ hai lớn nhất, ... Để biết "chọn chữ số này rồi thì phần sau còn kéo dài được tới đâu", ta dùng quy hoạch động theo số dư:
$f[n][0] = 0$, $f[n][r \ne 0] = -1$;
$f[i][r]$ $= \max\big(f[i+1][r],\ \ f[i+1][(10r + a_i) \bmod m] + 1\big)$ – bỏ chữ số $a_i$ hoặc lấy nó (vế phải chỉ tính khi khác $-1$).
Có bảng $f$ rồi, ta dựng đáp án từ trái sang phải: đang ở vị trí pos, số dư r, còn cần need chữ số nữa. Thử chữ số $c$ từ $9$ xuống $0$ (chữ số đầu tiên thì từ $9$ xuống $1$), lấy vị trí $j \ge pos$ sớm nhất có $a_j = c$ (lấy sớm nhất để để dành nhiều chữ số nhất cho phần sau). Nếu $f[j+1][(10r + c) \bmod m]$ $\ge need - 1$ thì chọn $c$. Chữ số đầu tiên thỏa mãn chính là chữ số lớn nhất có thể đặt ở vị trí này.
Em nhập $a$ (ngắn) và $m$ nhỏ rồi bấm Tiếp để xem bảng $f$ được điền từ phải sang trái, sau đó đáp án được dựng từng chữ số:
Cách 1Vét cạn mọi cách xoá – subtask 1
Với $a \le 10^{18}$, $a$ có tối đa 19 chữ số. Mỗi chữ số có 2 lựa chọn: giữ hoặc xoá, tổng cộng $2^{19} \approx 5 \cdot 10^5$ cách – thử hết được. Hàm đệ quy Try(i, val, cnt) xét chữ số thứ $i$, trong đó val là giá trị số tạo bởi các chữ số đã giữ, cnt là số chữ số đã giữ (để loại trường hợp xoá hết).
- Giữ chữ số $a_i$: giá trị mới là
val * 10 + a[i]. Các số 0 ở đầu tự động "biến mất" vì $0 \cdot 10 + 0 = 0$. - Giá trị lớn nhất có thể là $a \le 10^{18}$ – vừa kiểu
long long. best = -1nghĩa là chưa tìm thấy số nào chia hết cho $m$ → in!.
Kết quả chạy thật: bản C++ đúng 8/25 test – quá thời gian test 9–25 (test đúng chạy lâu nhất 0,011 giây). Bản Python đúng 5/25 test – quá thời gian test 4–5, 7, 9–25 (test đúng chạy lâu nhất 0,373 giây) – Python đệ quy $2^{19}$ lần cho mỗi bộ dữ liệu thì quá chậm với giới hạn 0,5 giây, chỉ qua được các test có $a$ ngắn.
Cách 2QHĐ theo số dư, lưu cả con số – subtask 2
Thay vì thử mọi tập con, ta duyệt các chữ số từ trái sang phải và với mỗi số dư $r$ chỉ giữ lại số lớn nhất (bắt đầu bằng chữ số khác 0) có số dư $r$ chọn được từ phần đã duyệt: best[r]. Khi gặp chữ số $d$:
- Nối $d$ vào cuối
best[r]được số có số dư $(10r + d) \bmod m$. - Hoặc $d$ đứng đầu (nếu $d \ne 0$), số dư $d \bmod m$.
Vì sao chỉ cần giữ số lớn nhất cho mỗi số dư? Hai số $x < y$ cùng số dư thì sau khi nối thêm cùng các chữ số phía sau, vẫn có $x' < y'$ và vẫn cùng số dư – nên $x$ không bao giờ tốt hơn $y$. Các số được lưu dạng xâu và so sánh theo quy tắc "dài hơn thì lớn hơn".
- Phải dùng mảng mới
nb(chép từbest): nếu cập nhật ngay vàobestthì một chữ số có thể bị dùng 2 lần trong cùng một lượt. - Hàm
lonHonso độ dài trước rồi mới so xâu. Xâu rỗng (chưa có số) luôn nhỏ hơn mọi số. - Cuối cùng nếu
best[0]rỗng thì xét trường hợp đặc biệt: $a$ có chữ số 0 → in0, ngược lại in!.
Kết quả chạy thật: bản C++ đúng 19/25 test – quá thời gian test 17, 19, 21–22, 24–25 (test đúng chạy lâu nhất 0,146 giây). Bản Python đúng 16/25 test – quá thời gian test 10, 15, 17, 19–22, 24–25 (test đúng chạy lâu nhất 0,353 giây).
Với $n = 100$ chữ số thì $n \cdot m \cdot n = 10^7$ phép xử lý ký tự cho mỗi bộ – ổn. Nhưng với $n = 1000$, mỗi bộ đã là $10^9$ (phải chép và so sánh xâu dài cả nghìn ký tự) → quá thời gian ở phần lớn subtask 3. Một vài test subtask 3 vẫn qua vì nhiều số dư không đạt được (xâu rỗng được bỏ qua ngay).
Cách 3QHĐ độ dài + tham lam – O(n·m)
Điểm chậm của cách 2 là lưu cả con số dài cả nghìn chữ số trong mỗi ô. Ý tưởng ở phần trên chỉ lưu một con số nhỏ trong mỗi ô: độ dài lớn nhất $f[i][r]$. Đáp án được dựng lại một lần bằng tham lam. Mảng phụ nxt[i][c] cho vị trí đầu tiên $\ge i$ có chữ số $c$, giúp tìm "vị trí sớm nhất" trong $O(1)$.
- Kiểu
short(2 byte) là đủ vì $f \le 1001$; bảng $1002 \times 1000$ chỉ tốn khoảng 2 MB. - Độ dài $L$ của đáp án tính riêng cho chữ số đầu khác 0: thử mọi $c = 1..9$ ở vị trí xuất hiện đầu tiên $j$, độ dài là $1 + f[j+1][c \bmod m]$.
- Trong vòng tham lam, chữ số đầu tiên duyệt $c = 9..1$, các chữ số sau duyệt $c = 9..0$. Điều kiện
f[j + 1][nr] >= need - 1nghĩa là "chọn $c$ ở vị trí $j$ rồi, phần còn lại vẫn đủ $need - 1$ chữ số để về số dư 0". Vòngforluôn tìm được $c$ vì đã biết có đáp án độ dài $L$. - Vì sao lấy vị trí sớm nhất của $c$? Nếu một đáp án dùng chữ số $c$ ở vị trí muộn hơn $j'$, ta đổi sang dùng $a_j$ ($j < j'$, cùng chữ số) thì phần sau vẫn chọn y như cũ được – không bao giờ thiệt.
Kết quả chạy thật: bản C++ đúng 25/25 test, chậm nhất 0,030 giây.
Bản Python: vòng lặp $n \cdot m = 10^6$ lần mỗi bộ (tổng $10^7$) bằng Python thuần chắc chắn quá 0,5 giây, nên mình dùng numpy để tính cả một cột $f[i][\cdot]$ trong một phép toán vector: f[i] = max(f[i+1], f[i+1][go[d]] + 1). Kết quả: 23/25 test – quá thời gian test 17, 22 (test đúng chạy lâu nhất 0,481 giây). Riêng thời gian nạp thư viện numpy đã tốn khoảng 0,1–0,2 giây nên với giới hạn 0,5 giây Python vẫn hụt ở vài test lớn nhất.
Tổng kếtKết quả
| Cách | C++ | Python |
|---|---|---|
| 1. Vét cạn $2^n$ | 8/25 test | 5/25 test |
| 2. QHĐ lưu cả số (xâu) | 19/25 test | 16/25 test |
| 3. QHĐ độ dài + tham lam | 25/25 test | 23/25 test |
0 (ví dụ $13570$, $m = 100$) và quên rằng không được xoá hết chữ số (ví dụ $a = 7$, $m = 3$ phải in ! chứ không phải "số rỗng").
Nhận xét
Đăng nhận xét