Số lớn nhất trên mỗi dòng

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

Đề bài

Cho mảng hai chiều $A$ gồm $n$ dòng và $n$ cột các số nguyên. Hãy tìm số lớn nhất trên mỗi dòng.

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 $n$ dòng, dòng thứ $i$ là số lớn nhất trên dòng thứ $i$ của mảng.

Giới hạn:

• $1 \le n \le 19$
• $|A[i][j]| < 10^{18}$ (các số có 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

3
1 3 4
8 4 2
4 2 8

Ví dụ 1 – output

4
8
8

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

Lời mở đầu

Tìm số lớn nhất của từng dòng – bài "tìm max" quen thuộc, chỉ là lặp lại cho mỗi dòng. Hai lỗi kinh điển: khởi tạo max = 0 (sai khi cả dòng âm) và quên đặt lại max khi sang dòng mới. Ghi chú: đề gốc ghi "$0 < m, n < 20$" cho ma trận vuông $n \times n$, mình viết lại $1 \le 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ưởngmax của từng dòngLờ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 19$, $|A[i][j]| < 10^{18}$.

Test	Nội dung kiểm tra
1	Ví dụ của đề
2–3, 5–6, 8–9, 12, 15, 17	Có dòng toàn số âm – max = 0 sai
5–6, 11–13, 15–16, 19–20	Số vượt int
4, 7, 10, 14, 18	Số lớn nhất ở các vị trí khác nhau, các số bằng nhau, toàn số 0

Ý tưởngLấy phần tử đầu dòng làm mốc

Với mỗi dòng i: đặt mx = a[i][0] (phần tử đầu dòng), rồi duyệt các phần tử còn lại, gặp số lớn hơn thì cập nhật. Hết dòng thì in mx.

Mốc phải là dữ liệu thật

Khởi tạo mx = 0 chỉ đúng khi dòng có số không âm. Một dòng toàn số âm như $-1, -2$ thì đáp án là $-1$, nhưng mx vẫn kẹt ở 0. Lấy a[i][0] làm mốc thì luôn đúng.

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ảiTìm max cho từng dòng

mx khai báo trong vòng lặp dòng và được gán bằng a[i][0] – vừa đặt lại cho dòng mới, vừa là mốc đúng.

C++▶ Chạy tay từng dòng codeMỗi dòng: mx = a[i][0], rồi so với a[i][1..n-1].

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Vòng trong bắt đầu từ j = 1 vì a[i][0] đã là mốc.
2. Giá trị tới $10^{18}$ nên dùng long long.
3. Python có hàm max(row), nhưng mình tự viết vòng lặp để thấy rõ thuật toán.

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

Thời gian$O(n^2)$

Kết quả chạy thật: bản C++ đúng 20/20 test, chạy lâu nhất 0.003s. Bản Python đúng 20/20 test, chạy lâu nhất 0.021s. 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ú
Khởi tạo mx = 0	11/20	sai test 2, 3, 5, 6, 8, 9, 12, 15, 17
Dùng int	11/20	sai test 5, 6, 11, 12, 13, 15, 16, 19, 20
Tìm nhầm max theo cột	6/20	sai test 1, 3, 4, 6, 8, 9, 11, 12, 13, 14, 15, 16, 17, 19
Không đặt lại mx khi sang dòng mới	7/20	sai test 3, 5, 6, 8, 9, 11, 12, 13, 14, 15, 16, 17, 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.003s	Full điểm
	Python	20/20	0.021s	Full điểm
mx = 0	C++	11/20	–	Mất 9 test
Dùng int	C++	11/20	–	Mất 9 test
Max theo cột	C++	6/20	–	Mất 14 test
Quên reset max	C++	7/20	–	Mất 13 test

Ghi chú của mình: mỗi khi bài yêu cầu kết quả "cho mỗi dòng", hãy chắc chắn các biến tích luỹ (tổng, max, biến đếm) được đặt lại ở đầu mỗi dòng.

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 😇