Chuẩn hóa các cặp đối xứng

Bối cảnh

Một hệ thống chuẩn hóa ma trận yêu cầu với mỗi cặp ô đối xứng qua đường chéo chính (i,j) và (j,i) với i<j, giá trị lớn hơn phải nằm ở tam giác trên. Bạn chỉ được phép đổi chỗ trực tiếp hai ô trong cùng một cặp đối xứng; các ô đường chéo chính không thay đổi.

Hãy thực hiện ít phép swap nhất để sau cùng a[i][j] >= a[j][i] với mọi i<j, đồng thời in số swap và ma trận thu được.

Vì mỗi cặp đối xứng độc lập, nếu cặp đã đúng thứ tự thì không nên động vào; nếu sai thì đúng một swap là bắt buộc và đủ. Bài Medium giúp người học rèn traversal chỉ trên nửa ma trận và thao tác biến đổi tại chỗ theo quan hệ giữa hai tọa độ.

Điểm quan trọng là không duyệt cả hai nửa, vì mỗi cặp chỉ được xét một lần.

Yêu cầu

1. Duyệt i=0..n-1, j=i+1..n-1.
2. Nếu a[i][j] < a[j][i], swap và tăng bộ đếm.
3. In kết quả.

Input

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

Output

Dòng 1: số swap tối thiểu. Sau đó ma trận chuẩn hóa.

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 4 7
2 5 8
3 6 9

Giải thích

Mỗi cặp đối xứng (i,j) và (j,i) với i<j được chuẩn hóa sao cho phần tử phía trên đường chéo chính không nhỏ hơn phần tử đối xứng phía dưới. Có ba cặp cần swap: 2<4, 3<7 và 6<8, nên bộ đếm bằng 3. Sau các swap, ma trận trở thành 1 4 7 / 2 5 8 / 3 6 9; các ô đường chéo chính 1,5,9 không đổi. Do đó output bắt đầu bằng 3 rồi là ma trận đã chuẩn hóa.

Ví dụ 2

Input

1
7

Output

0
7

Giải thích

Ma trận 1×1 không có cặp đối xứng ngoài đường chéo chính, vì vậy không có phép swap nào. Bộ đếm bằng 0 và phần tử 7 giữ nguyên. Output là 0 và ma trận một ô 7.

Thông tin học tập

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