Tìm số

Nguồn: Đề thi HSG Tin học cấp tỉnh Hậu Giang 2018 – 2019 Độ khó: Trung bình Duyệt Bitmask Xử lý xâu

Đề bài

Cho 2 số nguyên $N, M$ $(10^3 \le N \le 10^9,\ 10^2 \le M \le 10^9)$. Số nguyên $P$ tìm được bằng cách xoá 1 chữ số hoặc 1 số chữ số tại các vị trí bất kỳ trong số $N$ sao cho số $P$ là số lớn nhất chia hết cho $M$ $(M \le P)$. Hãy viết chương trình kiểm tra tính đúng của số nguyên $N, M$; nếu 2 số nguyên $N, M$ thoả mãn đề bài thì tìm số $P$.

Dữ liệu vào: cho trong tập tin timso.inp gồm 2 dòng:

• Dòng 1: chứa số nguyên $N$.
• Dòng 2: chứa số nguyên $M$.

Dữ liệu ra: xuất ra tập tin timso.out gồm 1 dòng:

• Nếu $N$ hoặc $M$ không thoả đề bài, ghi So nguyen N (M) khong thoa de bai, trong đó $N$, $M$ được thay thế bằng giá trị nhận từ tập tin.
• Nếu không tìm được số nguyên $P$, ghi Khong tim duoc so nguyen P.
• Nếu tìm được số nguyên $P$, ghi So nguyen tim duoc la P, trong đó $P$ được thay thế bằng giá trị tìm được.

Ví dụ 1 – input

1234
12

Ví dụ 1 – output

So nguyen 12 khong thoa de bai

Ví dụ 2 – input

12436
123

Ví dụ 2 – output

So nguyen tim duoc la 246

Lưu ý khi nộp bài

Trên CLUE OJ bài này đọc/ghi file y như đề: đọc từ timso.inp, ghi ra timso.out. Code bên dưới dùng if (fopen("timso.inp", "r")) { freopen(...); }: có file thì đọc/ghi file, không có thì đọc bàn phím – nên vừa nộp được vừa chạy thử được trên máy.

Giải thích ví dụ: ở ví dụ 1, $M = 12 < 10^2$ nên $M$ không thoả đề bài. Ở ví dụ 2, xoá chữ số 1 và 3 của 12436 được 246 $= 2 \cdot 123$ – số lớn nhất chia hết cho $123$ có thể tạo ra.

Lời mở đầu

Đây là bài thi HSG cấp tỉnh nên "bẫy" nằm ở phần kiểm tra dữ liệu nhiều hơn ở thuật toán: $N$ có thể là một xâu dài cả chục nghìn chữ số, phải in đúng định dạng, và phải hiểu chính xác "xoá 1 hoặc một số chữ số" nghĩa là gì. Mình sẽ phân tích kỹ các trường hợp đó rồi đi qua 2 cách tìm $P$: duyệt các bội của $M$ từ lớn xuống, và duyệt mọi cách xoá chữ số bằng bitmask.

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

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 OJ

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

Bộ test100 testÝ tưởngdãy con chữ sốCách 1bội của MCách 2bitmask

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

Số chữ số của N	Số test	Các test
4	26	5–30
5	10	31–40
6	10	41–50
7	10	51–60
8	10	61–70
9	29	71–99
N hoặc M sai giới hạn	5	1–4, 100

Loại đáp án	Số test	Các test
So nguyen ... khong thoa de bai	5	1–4, 100
Khong tim duoc so nguyen P	10	5–14
So nguyen tim duoc la P	85	15–99

• Bộ test có 100 test, đề không chia subtask. Với các test hợp lệ, $N$ có từ 4 đến 9 chữ số (không test nào có $N = 10^9$).
• 4 test đầu kiểm tra phần dữ liệu sai: $N = 379 < 10^3$, $N > 10^9$, $M = 73 < 10^2$, $M > 10^9$.
• Test 100 rất "hiểm": cả $N$ và $M$ đều là số gồm 10 000 chữ số 9! Đọc bằng int/long long là hỏng ngay – phải đọc bằng xâu. Đáp án in ra $N$ (vì kiểm tra $N$ trước), dòng output dài hơn 10 000 ký tự.
• 10 test (5–14) không tìm được $P$.

Mỗi cách giải ở dưới đều được chạy thật trên cả 100 test.

Ý tưởngP là một dãy con các chữ số của N

1. Kiểm tra dữ liệu. Đọc $N$, $M$ dưới dạng xâu. Xâu dài hơn 10 ký tự chắc chắn $> 10^9$; ngược lại đổi sang long long rồi so sánh với giới hạn. Kiểm tra $N$ trước, nếu sai in $N$; rồi mới kiểm tra $M$.

2. P là gì? Xoá một số chữ số của $N$ (giữ nguyên thứ tự các chữ số còn lại) – tức là $P$ là một dãy con các chữ số của $N$, và phải xoá ít nhất một chữ số nên $P$ có ít chữ số hơn $N$. Điều kiện $M \le P$ để loại $P = 0$ (số 0 chia hết cho mọi $M$ nhưng không được tính).

Nếu dãy con giữ lại bắt đầu bằng chữ số 0 (ví dụ giữ 0246) thì giá trị bằng dãy con ngắn hơn không có số 0 đầu (246) – vẫn là một cách xoá hợp lệ, nên không cần xử lý riêng.

3. Tìm P. $N$ có tối đa 10 chữ số, nên có tối đa $2^{10} = 1024$ cách giữ/xoá – thử hết là xong (Cách 2). Hoặc nghĩ ngược lại: thử các bội của $M$ từ lớn xuống nhỏ, bội đầu tiên là dãy con của $N$ chính là đáp án (Cách 1 – đúng tinh thần tham lam "thử cái lớn nhất trước").

Em nhập $N$ (tối đa 6 chữ số) và $M$ rồi bấm Tiếp để xem lần lượt các cách giữ chữ số (ô xanh là chữ số được giữ, ô gạch là chữ số bị xoá):

N = M =

Ví dụ nhanh:

Cách 1Duyệt bội của M từ lớn xuống nhỏ

$P$ có ít nhất 1 chữ số ít hơn $N$, nên nếu $N$ có $d$ chữ số thì $P < 10^{d-1}$. Bội lớn nhất của $M$ nhỏ hơn $10^{d-1}$ là $\left\lfloor \dfrac{10^{d-1} - 1}{M} \right\rfloor \cdot M$. Ta lùi dần từng bội $M$; với mỗi bội $p$ kiểm tra xâu to_string(p) có là dãy con của xâu $N$ không bằng hai con trỏ: đi dọc $N$, gặp chữ số trùng với chữ số đang chờ của $p$ thì tiến con trỏ của $p$.

C++▶ Chạy tay từng dòng codeCách 1: lùi dần các bội của M, kiểm tra dãy con bằng hai con trỏ.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Mỗi lần gọi laDayCon được gộp thành 1 bước ở dòng return của hàm (hình bên cạnh tô xanh các chữ số khớp được).

1. Hàm hopLe loại xâu dài hơn 10 ký tự trước khi gọi stoll – nhờ vậy test 100 (10 000 chữ số) không làm tràn số.
2. laDayCon so khớp tham lam: chữ số nào của $p$ cũng ghép với vị trí sớm nhất có thể trong $N$ – cách ghép này không bao giờ làm mất cơ hội của các chữ số sau.
3. Duyệt từ lớn xuống nên bội đầu tiên thoả là đáp án, return 0 luôn.
4. Số bội phải thử tệ nhất khoảng $\dfrac{10^{8}}{100} = 10^6$ (N có 9 chữ số, $M = 100$), mỗi lần kiểm tra tối đa 9 bước – vẫn rất nhanh.

Không gian$O(d)$

Thời gian$O\left(\dfrac{10^{d-1}}{M} \cdot d\right)$

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

Bản Python tuy qua hết nhưng chạy khá sát giới hạn ở các test $N$ có 9 chữ số và $M$ nhỏ (phải thử tới hàng trăm nghìn bội). Cách 2 dưới đây an toàn hơn nhiều vì không phụ thuộc $M$.

Cách 2Duyệt mọi cách xoá bằng bitmask

Đánh số các chữ số của $N$ từ trái sang: $0, 1, \ldots, d - 1$. Mỗi số mask từ $1$ tới $2^d - 2$ là một cách chọn: bit $i$ bằng 1 thì giữ chữ số thứ $i$. Bỏ mask = 0 (xoá hết) và mask = 2^d − 1 (không xoá gì). Ghép các chữ số được giữ thành $P$, nếu $P \ge M$ và chia hết cho $M$ thì cập nhật kết quả lớn nhất.

C++▶ Chạy tay từng dòng codeCách 2: thử mọi cách giữ/xoá chữ số bằng bitmask.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Vòng for i ghép chữ số được gộp thành 1 bước cho mỗi mask.

1. p = p * 10 + (sn[i] - '0'): ghép thêm chữ số vào bên phải $p$, chữ số đi theo đúng thứ tự trong $N$.
2. best = -1 nghĩa là chưa tìm được; cuối cùng còn $-1$ thì in Khong tim duoc so nguyen P.
3. Tổng số bước chỉ $2^d \cdot d \le 1024 \cdot 10$ – không phụ thuộc $M$.

Không gian$O(d)$

Thời gian$O(2^d \cdot d)$, $d \le 10$

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

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

Cách	Ngôn ngữ	Đúng	Lâu nhất (test đúng)	Ghi chú
1. Duyệt bội của M giảm dần	C++	100/100	0.040s	Full điểm
	Python	100/100	0.859s	Full điểm
2. Duyệt tập con chữ số (bitmask)	C++	100/100	0.006s	Full điểm
	Python	100/100	0.034s	Full điểm

Ghi chú của mình: thời gian là thời gian CPU trên máy của mình, giới hạn 1 giây/test. Cả hai cách đều full điểm; Cách 2 nhanh và ổn định hơn vì không phụ thuộc $M$. Với dạng đề thi HSG kiểu này, các bạn nhớ: đọc số "nghi ngờ" bằng xâu, kiểm tra dữ liệu theo đúng thứ tự đề nêu, và in chính xác từng ký tự của câu thông báo.

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 😇