Số chính phương trong ma trận (MT06)

Nguồn: CLUE OJ Độ khó: Trung bình Mảng 2 chiều Mã bài MT06

Đề bài

Nhập vào ma trận $A$ gồm $m$ dòng và $n$ cột các số nguyên. Hãy liệt kê các số chính phương có trong ma trận theo thứ tự tăng dần, mỗi giá trị chỉ liệt kê một lần (nếu một số chính phương xuất hiện nhiều lần thì cũng chỉ in một lần).

Số chính phương là số bằng bình phương của một số nguyên: $0, 1, 4, 9, 16, \ldots$ (số $0 = 0^2$ cũng là số chính phương; số âm không phải số chính phương).

Dữ liệu vào:

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

Kết quả:

In ra trên một dòng các số chính phương khác nhau có trong ma trận theo thứ tự tăng dần, cách nhau một dấu cách. Nếu ma trận không có số chính phương nào, in ra NOT FOUND.

Giới hạn:

• $2 \le m, n \le 100$
• $|A_{ij}| \le 10^4$

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

Ví dụ 1 – input

3 4
7 8 9 5
4 5 6 7
8 2 3 4

Ví dụ 1 – output

4 9

Giải thích:

• Các số chính phương trong ma trận là $9$, $4$ và $4$ (số $4$ xuất hiện hai lần nên chỉ in một lần).
• Sắp xếp tăng dần ta được $4, 9$.

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

Ý tưởng

Vì $|A_{ij}| \le 10^4$, em dùng một mảng đánh dấu co[0..10000]: gặp số $x$ là số chính phương thì đặt co[x] = true. Cuối cùng duyệt $x$ từ $0$ đến $10000$, in các $x$ có co[x] = true — tự động tăng dần và không trùng.

Kiểm tra $x$ chính phương: $x \ge 0$ và $r = \lfloor\sqrt{x}\rfloor$ thoả $r \cdot r = x$ (thầy chỉnh lại $r$ bằng hai vòng while để tránh sai số của sqrt).

Ví dụ: các số 9, 4, 4 được đánh dấu co[4] = co[9] = true → in 4 9. Nếu không đánh dấu được số nào thì in NOT FOUND.

Lưu ý / bẫy thường gặp

• Số 0 là số chính phương ($0 = 0^2$), đừng chỉ xét $x > 0$.
• Số âm không phải số chính phương: đừng lấy trị tuyệt đối.
• Mỗi số chỉ in một lần và phải tăng dần (không in theo thứ tự xuất hiện).
• Đừng quên trường hợp không có số nào → NOT FOUND.

Lời giải

Code chuẩn bên dưới đã chấm đúng toàn bộ 20 test trên CLUE OJ.

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 😇