Xóa chữ số để chia hết cho 3

Nguồn: CLUE OJ – Chương 45: Đồng dư modulo Độ khó: Trung bình Dấu hiệu chia hết cho 3 Quy hoạch động

Đề bài

Cho một số nguyên dương $N$, trong đó không có chữ số nào là $0$.

Gọi $k$ là số chữ số của $N$. Chúng ta muốn tạo ra một bội số của $3$ bằng cách xóa ít nhất $0$ và tối đa $k-1$ chữ số từ $N$ và nối các chữ số còn lại mà không thay đổi thứ tự.

Xác định xem có thể tạo ra một bội số của $3$ theo cách này không. Nếu có thể, tìm số chữ số tối thiểu cần phải xóa để tạo ra một số như vậy.

Input: dòng duy nhất chứa số nguyên $N$ $(1 \le N \le 10^{1\,000\,000})$, tức là $N$ có tối đa một triệu chữ số.

Output: nếu không thể tạo ra một bội số của $3$, in ra $-1$; ngược lại, in ra số chữ số tối thiểu cần xóa.

Subtask: $30\%$ số test đầu tiên có $N \le 10^{18}$; $70\%$ số test còn lại không có điều kiện gì thêm.

Ví dụ 1

35

Output: 1

Ví dụ 2

369

Output: 0

Ví dụ 3

6227384

Output: 1

Ví dụ 4

11

Output: -1

Giải thích: ví dụ 1 xóa chữ số $5$ được $3$. Ví dụ 2 không cần xóa vì $369$ đã chia hết cho $3$. Ví dụ 3 xóa chữ số $8$ được $622734$. Ví dụ 4: ta không được xóa hết cả 2 chữ số, mà $1$ và $11$ đều không chia hết cho $3$, nên in $-1$.

Lời mở đầu

$N$ dài tới một triệu chữ số, không kiểu số nào chứa nổi. Nhưng nhờ dấu hiệu chia hết cho 3: một số chia hết cho $3$ khi và chỉ khi tổng các chữ số chia hết cho $3$ – thứ tự các chữ số không quan trọng. Bài toán trở thành: bỏ ít chữ số nhất để tổng còn lại chia hết cho $3$. Mình đi từ cách thử mọi cách xóa, tới quy hoạch động theo số dư, rồi tới lời giải chỉ cần đếm.

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

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

Bộ test100 test, 2 mứcÝ tưởngtổng chữ số mod 3Cách 1thử mọi cách xóaCách 2QHĐ theo số dưCách 3đếm + xét trường hợpTổng kếtkết quả chạy thật

Bộ testBộ test chính thức có gì?

Test	Số chữ số $k$	Tổng chữ số mod 3	Đáp án
1 – 30	2 – 17	0: 7 test, 1: 10 test, 2: 13 test	$-1$ (1 test), $0$, $1$
31 – 100	đúng $1\,000\,000$	0: 28 test, 1: 23 test, 2: 19 test	$0$, $1$

• Test 1–30 có $N < 10^{18}$ (tối đa 17 chữ số) – đúng $30\%$ của đề; 70 test còn lại đều dài đúng một triệu chữ số.
• Chỉ có test 4 (22) có đáp án $-1$. Bộ test không có test nào đáp án bằng $2$ – nhưng lời giải vẫn phải xử lý trường hợp đó (ví dụ 223 phải xóa 2 chữ số $2$).
• Không test nào chứa chữ số $0$, đúng như đề.

Subtask	Điều kiện	Các test	Cách ăn được
1 (30%)	$N \le 10^{18}$	1 – 30	Cách 1, 2, 3
2 (70%)	tới $10^6$ chữ số	31 – 100	Cách 2, 3

Ý tưởngChỉ cần tổng các chữ số mod 3

Vì $10 \equiv 1 \pmod 3$ nên $10^i \equiv 1 \pmod 3$ với mọi $i$, suy ra:

Dấu hiệu chia hết cho 3

$$\overline{d_1 d_2 \ldots d_k} = \sum d_i \cdot 10^{k-i} \equiv \sum d_i \pmod 3$$

Xóa chữ số nào thì tổng giảm đúng chữ số đó. Gọi $S = (\text{tổng}) \bmod 3$:

• $S = 0$: không cần xóa – đáp án $0$.
• $S \ne 0$: xóa một chữ số có cùng số dư $S$ là đủ (nếu còn ít nhất 1 chữ số).
• Không có chữ số dư $S$: xóa hai chữ số có số dư $3 - S$ (vì $2(3-S) \equiv S \pmod 3$), nếu còn ít nhất 1 chữ số.
• Không làm được cả hai: đáp án $-1$. Không bao giờ cần xóa 3 chữ số trở lên.

Em nhập số $N$ rồi bấm Tiếp để xem từng bước:

N =

Ví dụ nhanh:

Cách 1Thử mọi cách giữ / xóa – O(2^k)

Với mỗi chữ số ta có 2 lựa chọn: giữ hoặc xóa. Dùng đệ quy thử hết $2^k$ cách, cách nào giữ ít nhất 1 chữ số và tổng các chữ số giữ lại chia hết cho $3$ thì cập nhật số chữ số giữ lại nhiều nhất. (Ở đây mình đã dùng luôn dấu hiệu chia hết cho 3, không cần tạo số thật.)

C++▶ Chạy tay từng dòng codeCách 1: đệ quy dfs(i, sum, kept) – nhánh trái giữ s[i], nhánh phải xóa s[i].

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Có $2^k$ lá đệ quy: với $k = 17$ khoảng $1{,}3 \cdot 10^5$ – rất nhanh; với $k = 10^6$ thì hoàn toàn không thể.
• Đây là cách "chắc chắn đúng", mình dùng nó để kiểm tra chéo các cách sau trên hàng trăm số ngẫu nhiên.

Không gian$O(k)$ (độ sâu đệ quy)

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

Kết quả chạy thật: bản C++ đúng 30/100 test (Subtask 1: 30/30, Subtask 2: 0/70), chạy lâu nhất 0,005s ở subtask 1; 70 test một triệu chữ số đều quá thời gian. Bản Python đúng 30/100 (Subtask 1: 30/30, Subtask 2: 0/70).

Cách 2Quy hoạch động theo số dư – O(3k)

Không cần biết giữ chữ số nào, chỉ cần biết tổng các chữ số giữ lại dư mấy khi chia 3. Gọi $dp[r]$ là số chữ số giữ lại nhiều nhất (trong các chữ số đã xét, giữ ít nhất 1) sao cho tổng chia 3 dư $r$; $-1$ nếu chưa có cách nào. Xét thêm chữ số $d$:

Chuyển trạng thái

$$dp'[(r + d) \bmod 3] = \max\big(dp'[(r+d) \bmod 3],\ dp[r] + 1\big), \qquad dp'[d \bmod 3] \ge 1$$

(còn lại giữ nguyên $dp' = dp$ – tức là xóa chữ số $d$). Đáp án là $k - dp[0]$, hoặc $-1$ nếu $dp[0] = -1$.

C++▶ Chạy tay từng dòng codeCách 2: dp[r] = số chữ số giữ lại nhiều nhất, tổng chia 3 dư r.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Mỗi chữ số chỉ tốn vài phép so sánh, tổng cộng khoảng $3 \cdot 10^6$ thao tác cho $k = 10^6$.
• Ưu điểm của cách này: tổng quát – thay $3$ bằng số $m$ bất kỳ (ví dụ "xóa ít nhất để chia hết cho 9") vẫn dùng được với độ phức tạp $O(m \cdot k)$.
• Bản Python phải chạy vòng lặp một triệu lần với nhiều phép tính bên trong, nên chậm.

Không gian$O(k)$ (lưu xâu)

Thời gian$O(3k)$

Kết quả chạy thật: bản C++ đúng 100/100 test, lâu nhất 0,026s. Bản Python đúng 30/100 (Subtask 1: 30/30, Subtask 2: 0/70).

Cách 3Đếm số dư + xét 3 trường hợp – O(k)

Làm đúng phần Ý tưởng: đếm số chữ số dư $1$, dư $2$ và tổng mod 3, rồi xét: tổng chia hết → $0$; có chữ số cùng số dư $S$ (và $k > 1$) → $1$; có ít nhất 2 chữ số dư $3 - S$ (và $k > 2$) → $2$; còn lại → $-1$.

C++▶ Chạy tay từng dòng codeCách 3: đếm cnt[0..2] và tổng mod 3, rồi xét trường hợp.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Điều kiện $k > 1$ và $k > 2$ đảm bảo sau khi xóa vẫn còn ít nhất 1 chữ số (đề không cho xóa hết).
• Bản Python dùng s.count('1'), … chạy bằng mã C bên trong nên rất nhanh, thay vì vòng lặp từng kí tự.

Không gian$O(k)$ (lưu xâu)

Thời gian$O(k)$

Kết quả chạy thật: bản C++ đúng 100/100 test, lâu nhất 0,014s; bản Python đúng 100/100, lâu nhất 0,057s.

Tổng kếtKết quả chạy thật trên bộ test

Mình chấm cả 3 cách (C++ và Python) trên toàn bộ 100 test với giới hạn 1 giây, đo thời gian CPU:

Lời giải	Subtask 1 test 1–30	Subtask 2 test 31–100	Tổng	CPU lớn nhất (test đúng)
Cách 1 – C++	30/30	0/70	30/100	0,005s
Cách 1 – Python	30/30	0/70	30/100	0,116s
Cách 2 – C++	30/30	70/70	100/100	0,026s
Cách 2 – Python	30/30	0/70	30/100	0,038s
Cách 3 – C++	30/30	70/70	100/100	0,014s
Cách 3 – Python	30/30	70/70	100/100	0,057s

Ghi chú của mình: chìa khóa của bài là dấu hiệu chia hết cho 3 – biến một số một triệu chữ số thành chỉ một con số $0, 1, 2$. Cách 2 (quy hoạch động theo số dư) là kỹ thuật tổng quát nên nhớ; cách 3 là lời giải gọn nhất cho riêng số 3. Đừng quên điều kiện "không được xóa hết" – đó là lý do 11 và 22 cho đáp án $-1$.

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 😇