Bội ba

Nguồn: CLUE OJ Độ khó: Dễ Vòng lặp Đếm

Đề bài

Cho hai số nguyên không âm $a$ và $b$. Hãy đếm xem trong đoạn $[a, b]$ (gồm cả $a$ và $b$) có bao nhiêu số chia hết cho $3$.

Lưu ý: số $0$ cũng chia hết cho $3$.

Dữ liệu vào:

Một dòng gồm hai số nguyên $a$ và $b$ cách nhau bởi dấu cách.

Kết quả:

Số lượng số chia hết cho $3$ trong đoạn $[a, b]$.

Giới hạn:

• $0 \le a \le b \le 10^6$

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

1 10

Ví dụ 1 – output

3

Ví dụ 2 – input

1 4

Ví dụ 2 – output

1

• Ví dụ 1: các số chia hết cho $3$ trong đoạn $[1, 10]$ là $3, 6, 9$.
• Ví dụ 2: chỉ có số $3$.

Nguồn: phỏng theo bài "BỘI BA" – vinhdinhcoder.net (chủ đề Lặp FOR).

Lời mở đầu

Bài đếm cơ bản: duyệt từng số trong đoạn $[a, b]$, số nào chia hết cho 3 thì tăng biến đếm. Hai chỗ dễ sai là hai đầu mút $a$, $b$ và số 0. Ghi chú: đề gốc ghi "hai số nguyên dương" nhưng ràng buộc lại cho $a = 0$; mình giữ $0 \le a$ và ghi rõ trong đề rằng số 0 cũng chia hết cho 3.

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ưởngduyệt và đếmLờ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. Mọi test có $0 \le a \le b \le 10^6$.

Test	Nội dung kiểm tra
1–2	Ví dụ đề
3, 4, 8, 11, 19	$a = 0$ – số 0 cũng phải được đếm
5, 6, 9, 15	$a = b$: chia hết cho 3 (đáp án 1) hoặc không (đáp án 0)
7, 13, 14, 17, 20	Hai đầu mút là bội của 3 – bẫy bỏ sót đầu mút
10, 12, 16, 18	Đoạn dài tới $10^6$ số

Ý tưởngDuyệt từng số, gặp bội của 3 thì đếm

Biến dem = 0. Cho i chạy từ $a$ tới $b$ (kể cả $b$: điều kiện i <= b), nếu i % 3 == 0 thì dem++.

Đoạn dài nhất có $10^6 + 1$ số – vòng lặp chạy rất nhanh, cả C++ lẫn Python đều kịp.

Số 0 và hai đầu mút

$0 \% 3 = 0$ nên số 0 chia hết cho 3: đoạn $[0, 0]$ có đáp án là 1. Vòng lặp for(i = a; i <= b; i++) tự động xử lý đúng mọi trường hợp; còn các "công thức nhanh" như b / 3 - a / 3 rất dễ lệch 1 ở đầu mút.

Em nhập $a$, $b$ rồi bấm Tiếp để xem vòng lặp xét từng số:

a = b =

Ví dụ nhanh:

Lời giảiVòng lặp for và biến đếm

Mẫu "duyệt – kiểm tra – đếm" quen thuộc.

C++▶ Chạy tay từng dòng codeDuyệt i từ a tới b, đếm các số chia hết cho 3.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Sau 15 lần lặp, phần còn lại được "tua nhanh" trong một bước.

1. Python: range(a, b + 1) mới gồm cả $b$ – range(a, b) dừng ở $b - 1$.
2. Muốn nhanh hơn nữa có thể dùng công thức, nhưng phải cẩn thận: số bội của 3 trong $[1, b]$ là $b / 3$, còn số 0 phải tính riêng.

Không gian$O(1)$

Thời gian$O(b - a)$

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.131s. 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ú
Điều kiện lặp i < b (bỏ sót $b$)	12/20	sai test 3, 5, 7, 10, 13, 16, 17, 19
Duyệt khoảng mở: từ $a + 1$ tới $b - 1$	7/20	sai test 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20
Công thức b / 3 - a / 3	8/20	sai test 3, 4, 5, 7, 8, 11, 13, 14, 16, 17, 19, 20
Công thức b / 3 - (a - 1) / 3 (quên số 0)	15/20	sai test 3, 4, 8, 11, 19

Công thức b/3 − (a−1)/3 sai ở đâu?

Với $a \ge 1$ công thức này đúng. Nhưng khi $a = 0$: (0 - 1) / 3 trong C++ bằng $0$ (chia nguyên làm tròn về 0, không phải $-1$), nên số 0 không được đếm. Vòng lặp thì không gặp rắc rối này.

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.131s	Full điểm
i < b	C++	12/20	–	Mất 8 test
Khoảng mở	C++	7/20	–	Mất 13 test
b/3 − a/3	C++	8/20	–	Mất 12 test
Quên số 0	C++	15/20	–	Mất 5 test

Ghi chú của mình: khi đếm trên đoạn $[a, b]$, hãy thử ngay các trường hợp biên: $a = b$, $a = 0$, và $a$, $b$ đều thoả điều kiện.

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 😇