Tổng đường chéo chính

Nguồn: CLUE OJ Độ khó: Dễ Mảng 2 chiều Đường chéo

Đề bài

Cho mảng hai chiều $A$ gồm $n$ dòng và $n$ cột các số nguyên (ma trận vuông). Hãy tính tổng các số trên đường chéo chính. Một phần tử thuộc đường chéo chính khi chỉ số dòng bằng chỉ số cột.

Dữ liệu vào:

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

Kết quả:

In ra tổng các số trên đường chéo chính.

Giới hạn:

• $1 \le n \le 110$
• $|A[i][j]| \le 10^{16}$

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

4
1 3 4 5
8 4 2 7
4 2 8 6
1 3 2 3

Ví dụ 1 – output

16

Các số trên đường chéo chính là $1, 4, 8, 3$, tổng bằng $16$.

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

Lời mở đầu

Đường chéo chính của ma trận vuông gồm các ô có chỉ số dòng bằng chỉ số cột: $a[0][0], a[1][1], \ldots$ Không cần hai vòng lặp – một vòng for là đủ. Ghi chú: đề gốc cho $|A[i][j]| < 10^{18}$ với $n$ tới 110 thì tổng đường chéo có thể tới $1{,}1 \cdot 10^{20}$, tràn cả long long; để vẫn đúng tinh thần bài cơ bản, mình hạ ràng buộc thành $|A[i][j]| \le 10^{16}$ (tổng tối đa $1{,}1 \cdot 10^{18}$). Đề gốc còn ghi "$0 < m, n < 111$" dù ma trận vuông chỉ có $n$, mình viết lại $1 \le n \le 110$.

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ưởnga[i][i]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. Mọi test có $1 \le n \le 110$, $|A[i][j]| \le 10^{16}$.

Test	Nội dung kiểm tra
1	Ví dụ của đề
2–10	Ma trận nhỏ: 1 ô, đường chéo âm, đường chéo phụ khác chéo chính, số vượt int
11–13, 16, 19	Tổng tới $\pm 1{,}1 \cdot 10^{18}$ – int tràn, double làm tròn sai
14–15, 17–18, 20	Ma trận lớn với số nhỏ, đường chéo phụ toàn số lớn còn chéo chính bằng 0

Ý tưởngChỉ số dòng bằng chỉ số cột

Phần tử ở dòng i thuộc đường chéo chính khi cột của nó cũng là i, tức là ô a[i][i]. Mỗi dòng có đúng một ô như vậy, nên:

for (i = 0; i < n; i++) tong += a[i][i];

Chéo chính và chéo phụ

Đường chéo phụ đi từ góc trên phải xuống góc dưới trái, gồm các ô a[i][n − 1 − i]. Đề hỏi chéo chính (góc trên trái → góc dưới phải).

Em nhập ma trận vuông (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ảiMột vòng for qua a[i][i]

Vẫn phải đọc đủ $n^2$ số của ma trận, nhưng phần tính toán chỉ có $n$ phép cộng.

C++▶ Chạy tay từng dòng codeCộng các ô a[i][i] trên đường chéo chính.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Không cần vòng lặp thứ hai kiểm tra if (i == j) – viết thẳng a[i][i] gọn và nhanh hơn.
2. Tổng có thể tới $1{,}1 \cdot 10^{18}$, vẫn vừa long long.
3. Python: tong += a[i][i] y hệt.

Không gian$O(n^2)$

Thời gian$O(n)$ (chưa kể đọc dữ liệu $O(n^2)$)

Kết quả chạy thật: bản C++ đúng 20/20 test, chạy lâu nhất 0.012s. Bản Python đúng 20/20 test, chạy lâu nhất 0.024s. 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ú
Cộng bằng int	11/20	sai test 6, 7, 10, 11, 12, 13, 15, 16, 19
Lấy nhầm đường chéo phụ a[i][n − 1 − i]	4/20	sai test 1, 3, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19
Cộng cả ma trận	1/20	sai test 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
Cộng bằng double	15/20	sai test 11, 12, 13, 16, 19

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.012s	Full điểm
	Python	20/20	0.024s	Full điểm
Tổng kiểu int	C++	11/20	–	Mất 9 test
Chéo phụ	C++	4/20	–	Mất 16 test
Cộng cả ma trận	C++	1/20	–	Mất 19 test
Dùng double	C++	15/20	–	Mất 5 test

Ghi chú của mình: nhớ hai công thức: chéo chính a[i][i], chéo phụ a[i][n − 1 − i] (chỉ số từ 0).

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 😇