Khôi phục ma trận đối xứng nhỏ nhất

Bối cảnh

Một hệ thống lưu quan hệ giữa n đối tượng bằng ma trận vuông. Sau một lần đồng bộ lỗi, ma trận có thể không còn đối xứng qua đường chéo chính, trong khi định dạng chuẩn yêu cầu a[i][j] = a[j][i] với mọi cặp.

Mỗi lần sửa, bạn được phép thay giá trị của một ô. Hãy biến ma trận thành đối xứng với số lần sửa ít nhất. Nếu một cặp đối xứng (i,j) và (j,i) đang khác nhau, chỉ cần sửa một trong hai ô. Trong số các ma trận đạt số lần sửa tối thiểu, hệ thống yêu cầu kết quả "nhỏ" hơn theo quy tắc cục bộ: với mỗi cặp khác nhau, chọn giá trị nhỏ hơn trong hai giá trị ban đầu làm giá trị chung. Các ô trên đường chéo chính giữ nguyên.

Bài Medium yêu cầu nhận ra mỗi cặp đối xứng là một quyết định độc lập và phải tránh xử lý hai lần cùng một cặp.

Đây không chỉ là kiểm tra YES/NO. Bạn phải xây dựng một ma trận chuẩn cụ thể và đếm số thay đổi tối thiểu.

Yêu cầu

1. Chỉ duyệt các cặp i<j.
2. Nếu hai ô bằng nhau, giữ nguyên.
3. Nếu khác nhau, tăng changes và gán cả hai bằng min của cặp.
4. In số thay đổi rồi ma trận kết quả.

Input

Dòng 1: n; sau đó n dòng ma trận vuông.

Output

Dòng 1: số ô cần thay tối thiểu. Sau đó in ma trận đối xứng theo quy tắc trên.

Ràng buộc

1 ≤ n ≤ 100, |a[i][j]| ≤ 10^9.

Ví dụ 1

Input

3
1 2 3
4 5 6
7 8 9

Output

3
1 2 3
2 5 6
3 6 9

Giải thích

Ta xét từng cặp đối xứng qua đường chéo chính. Cặp (0,1)=2 và (1,0)=4 khác nhau nên cần 1 thay đổi và cả hai được chuẩn hóa về min=2; tương tự cặp (0,2)=3 với (2,0)=7 về 3, và (1,2)=6 với (2,1)=8 về 6. Có đúng 3 cặp cần chỉnh, còn đường chéo chính 1,5,9 giữ nguyên. Ma trận kết quả vì thế là 1 2 3 / 2 5 6 / 3 6 9, và dòng đầu in số thay đổi 3.

Ví dụ 2

Input

1
5

Output

0
5

Giải thích

Với n=1 chỉ có ô đường chéo chính (0,0)=5; không tồn tại cặp (i,j) với i<j để so sánh đối xứng. Vì vậy số thay đổi là 0 và ma trận giữ nguyên một ô 5. Output gồm 0 rồi 5.

Thông tin học tập

• Module: M03
• Buổi: B12
• Loại bài: HOMEWORK
• Độ khó: Medium
• Concepts: 2D static arrays, symmetry, pair processing, in-place transformation, lexicographic choice
• Giới hạn kiến thức: B01-B12
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100