Đếm số chia hết cho 3 trong ma trận

Nguồn: CLUE OJ Độ khó: Dễ Mảng 2 chiều Đếm

Đề bài

Cho ma trận số nguyên $A$ gồm $m$ dòng và $n$ cột. Hãy đếm số lượng các số chia hết cho $3$ có trong ma trận (số $0$ và các số âm như $-6$ cũng chia hết cho $3$).

Dữ liệu vào:

• Dòng đầu tiên gồm hai số nguyên dương $m, n$.
• $m$ dòng tiếp theo, mỗi dòng gồm $n$ số nguyên là một dòng của ma trận $A$.

Kết quả:

In ra số lượng đếm được.

Giới hạn:

• $1 \le m, n \le 19$
• $|A[i][j]| < 10^{18}$

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

3 4
1 3 4 6
8 4 2 9
4 2 8 6

Ví dụ 1 – output

4

Các số chia hết cho $3$ là $3, 6, 9, 6$ – có $4$ số.

Nguồn: phỏng theo bài "MẢNG 6.1" – vinhdinhcoder.net (chủ đề Mảng 2 chiều).

Lời mở đầu

Bài đếm cơ bản trên ma trận: duyệt mọi ô, ô nào chia hết cho 3 thì tăng biến đếm. Cần nhớ: số 0 và số âm như $-6$ cũng chia hết cho 3, và các số tới $10^{18}$ không vừa int. Ghi chú: đề gốc ghi "$0 < m, n < 20$", mình viết lại $1 \le m, n \le 19$.

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ưởngx % 3 == 0Lờ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ó $1 \le m, n \le 19$, $|A[i][j]| < 10^{18}$.

Test	Nội dung kiểm tra
1	Ví dụ của đề
2–3, 5–6, 11–13, 15–19	Có số 0 và số âm chia hết cho 3 – chỉ đếm số dương sẽ sai
8, 11, 13–16, 18	Số vượt int – đọc bằng int bị sai
1, 6, 8–9, 15–16, 18	Ma trận không vuông, một dòng, một cột

Ý tưởngDuyệt mọi ô và đếm

Hai vòng for lồng nhau đi qua mọi ô a[i][j]; nếu a[i][j] % 3 == 0 thì dem++.

0 và số âm

$0 = 3 \cdot 0$ nên 0 chia hết cho 3; $-6 = 3 \cdot (-2)$ nên $-6$ cũng vậy. Trong C++, -6 % 3 == 0 và 0 % 3 == 0, nên điều kiện x % 3 == 0 tự xử lý đúng – đừng thêm x > 0.

Em nhập ma trận (các dòng cách nhau bởi dấu ;) rồi bấm Tiếp:

Ma trận =

Ví dụ nhanh:

Lời giảiHai vòng for và một biến đếm

Biến đếm tối đa $19 \cdot 19 = 361$ nên int là đủ, còn các phần tử phải là long long.

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

Dữ liệu vào (stdin) – sửa thoải mái3 4 1 3 4 6 8 4 2 9 4 2 8 6

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. a[i][j] % 3 == 0 đúng cho cả số âm và số 0.
2. Nếu đọc số $3 \cdot 10^9$ vào biến int, cin sẽ báo lỗi và các số sau đều đọc sai – luôn kiểm tra giới hạn giá trị trước khi chọn kiểu.
3. Python: x % 3 == 0 y hệt.

Không gian$O(m \cdot n)$

Thời gian$O(m \cdot n)$

Kết quả chạy thật: bản C++ đúng 20/20 test, chạy lâu nhất 0.002s. Bản Python đúng 20/20 test, chạy lâu nhất 0.017s. 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ú
Dùng int	13/20	sai test 8, 11, 13, 14, 15, 16, 18
Chỉ đếm số dương (x > 0 && x % 3 == 0)	6/20	sai test 2, 3, 5, 6, 7, 8, 11, 12, 13, 15, 16, 17, 18, 19
Đọc nhầm thứ tự n, m	13/20	sai test 1, 6, 8, 9, 15, 16, 18

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.002s	Full điểm
	Python	20/20	0.017s	Full điểm
Dùng int	C++	13/20	–	Mất 7 test
Chỉ đếm số dương	C++	6/20	–	Mất 14 test
Đọc nhầm m, n	C++	13/20	–	Mất 7 test

Ghi chú của mình: "chia hết cho $k$" nghĩa là $x = k \cdot q$ với $q$ nguyên – bao gồm cả $q = 0$ và $q$ âm.

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 😇