Đổi số

Nguồn: CLUE OJ Độ khó: Dễ Vòng lặp Chữ số

Đề bài

Xu cho Xốp một số nguyên dương $N$. Xốp được thay đổi đúng một chữ số bất kỳ của $N$ (thay bằng một chữ số khác từ $0$ đến $9$) để tạo thành một số mới sao cho:

• Số mới không có chữ số 0 ở đầu (chữ số đầu tiên của số mới phải khác $0$; khi $N$ chỉ có một chữ số thì cũng không được tạo ra số $0$);
• Số mới khác số ban đầu;
• Số mới chia hết cho $3$.

Hỏi Xốp có thể tạo ra được bao nhiêu số khác nhau?

Dữ liệu vào:

Một số nguyên dương $N$.

Kết quả:

Số lượng số khác nhau Xốp có thể tạo ra.

Giới hạn:

• $1 \le N < 10^9$ ($N$ có tối đa $9$ chữ số)

Subtask:

• Subtask 1 (40% số điểm): $N$ có $1$ chữ số.
• Subtask 2 (20% số điểm): $N$ có $2$ chữ số.
• Subtask 3 (20% số điểm): $N$ có $3$ chữ số.
• Subtask 4 (20% số điểm): không có ràng buộc gì thêm.

Giới hạn thời gian: 1 giây, bộ nhớ: 256 MB. Dữ liệu nhập từ bàn phím và in ra màn hình.

Ví dụ 1 – input

13

Ví dụ 1 – output

6

Ví dụ 2 – input

3

Ví dụ 2 – output

2

• Ví dụ 1: Xốp tạo được $6$ số: $12, 15, 18$ (đổi chữ số hàng đơn vị) và $33, 63, 93$ (đổi chữ số hàng chục).
• Ví dụ 2: Xốp tạo được $6$ và $9$ (không được tạo số $0$, và $3$ trùng số ban đầu).

Nguồn: phỏng theo bài "ĐỔI SỐ" – vinhdinhcoder.net (chủ đề Lặp FOR).

Lời mở đầu

Thay đúng một chữ số của $N$ để được số chia hết cho 3. Thử mọi số có cùng số chữ số thì với $N$ có 9 chữ số phải thử gần $10^9$ số – quá chậm. Nhưng chỉ có tối đa $9$ vị trí, mỗi vị trí $10$ chữ số để thay: chưa tới $90$ trường hợp! Kết hợp với dấu hiệu chia hết cho 3 (tổng chữ số chia hết cho 3), ta giải xong chỉ bằng vòng lặp, không cần mảng hay xâu. Ghi chú: đề gốc không nói rõ khi $N$ có 1 chữ số thì có được tạo ra số 0 không; mình chốt số mới phải có chữ số đầu khác 0 (nên không tạo số 0) và ghi rõ trong đề.

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ộ test20 testÝ tưởngthử từng vị tríLời giảicode C++ / PythonCái bẫycách làm saiTổng kếtkết quả

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

Bộ test có 20 test, mỗi test đúng được 1 phần điểm như nhau. Test 1–8: $N$ có 1 chữ số; test 9–12: 2 chữ số; test 13–16: 3 chữ số; test 17–20: tới 9 chữ số.

Test	Nội dung kiểm tra
1–8	$N$ có 1 chữ số: không được thay thành 0
9–12	$N$ có 2 chữ số (gồm ví dụ đề 13), có chữ số 0, $N$ chia hết / không chia hết cho 3
13–16	$N$ có 3 chữ số: $100, 312, 999, 507$
17–20	$N$ tới 9 chữ số: $999\,999\,999$, $100\,000\,000$, $123\,456\,789$, số ngẫu nhiên – thử mọi số sẽ quá thời gian

Ý tưởngThử từng vị trí, từng chữ số thay thế

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ố của nó chia hết cho 3. Gọi $s$ là tổng chữ số của $N$. Nếu thay chữ số $d$ ở một vị trí bằng chữ số $c$, tổng chữ số mới là $s - d + c$. Vậy số mới chia hết cho 3 khi (s - d + c) % 3 == 0.

Duyệt các vị trí không cần mảng: cho p chạy $1, 10, 100, \ldots$ chừng nào $p \le N$. Chữ số ở vị trí ứng với p là N / p % 10; đó là chữ số đầu tiên (hàng cao nhất) khi p * 10 > N.

Với mỗi vị trí, thử $c = 0, 1, \ldots, 9$ và bỏ qua:

• $c = d$ – số mới phải khác số ban đầu;
• $c = 0$ ở chữ số đầu – không được có số 0 ở đầu.

Có bị đếm trùng không?

Hai số tạo từ cùng một vị trí khác nhau vì chữ số thay khác nhau; hai số tạo từ hai vị trí khác nhau thì khác nhau ở cả hai vị trí đó. Vậy mọi số tạo ra đều khác nhau – chỉ cần đếm, không cần lưu lại.

Em nhập $N$ rồi bấm Tiếp để xem chương trình thử từng vị trí chữ số:

N =

Ví dụ nhanh:

Lời giảiHai vòng lặp lồng nhau

Vòng ngoài duyệt vị trí chữ số (biến p), vòng trong thử chữ số thay thế c. Lệnh continue bỏ qua các chữ số không hợp lệ.

C++▶ Chạy tay từng dòng codeTính tổng chữ số, rồi với mỗi vị trí thử 10 chữ số thay thế.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Vòng lặp trong (thử c = 0 … 9) được gộp thành hai bước cho gọn.

1. p khai báo long long vì khi $N$ có 9 chữ số, p sẽ nhân lên tới $10^9$ và p * 10 tới $10^{10}$ – vượt int.
2. s - d + c không bao giờ âm vì $s \ge d$.
3. Python dùng while cho vòng ngoài vì p nhân 10 sau mỗi lần lặp.

Không gian$O(1)$

Thời gian$O(\log N)$ (tối đa $9 \times 10$ lần thử)

Kết quả chạy thật: bản C++ đúng 20/20 test, chạy lâu nhất 0.006s. Bản Python đúng 20/20 test, chạy lâu nhất 0.023s. Full điểm.

Cái bẫyNhững cách làm sai hay gặp

Các cách làm sai mình đã chấm thử trên bộ test:

Cách làm sai	Đúng	Ghi chú
Cho phép thay chữ số đầu bằng 0	5/20	sai test 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 13, 14, 15, 17, 18
Quên điều kiện số mới khác số ban đầu ($c \ne d$)	10/20	sai test 1, 3, 4, 10, 11, 14, 15, 16, 17, 19
Chỉ kiểm tra chữ số mới $c$ chia hết cho 3	14/20	sai test 11, 12, 14, 16, 19, 20
Không thử chữ số 0 ở mọi vị trí (cả các vị trí không phải đầu)	15/20	sai test 12, 15, 17, 19, 20
Thử mọi số có cùng số chữ số, đếm số vị trí khác nhau	16/20	sai test 17, 18, 19, 20

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

Cách	Ngôn ngữ	Đúng	Lâu nhất	Ghi chú
Lời giải chuẩn	C++	20/20	0.006s	Full điểm
	Python	20/20	0.023s	Full điểm
Cho số 0 ở đầu	C++	5/20	–	Mất 15 test
Quên c ≠ d	C++	10/20	–	Mất 10 test
Chỉ xét c	C++	14/20	–	Mất 6 test
Bỏ chữ số 0	C++	15/20	–	Mất 5 test
Thử mọi số	C++	16/20	–	Mất 4 test

Ghi chú của mình: khi đề nói "thay đổi một thứ", hãy đếm xem có bao nhiêu cách thay – thường ít hơn rất nhiều so với việc thử mọi kết quả có thể.

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 😇