VM 14 Bài 11 - Bảng quan hệ

View as PDF

Submit solution

Points: 1.25 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
RR
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho một ma trận ~a~ kích thước ~n \times n~ chỉ gồm các giá trị ~\{-2, -1, 0, 1, 2\}~. Các hàng của ma trận ~a~ được đánh số từ ~1~ đến ~n~ từ trên xuống dưới. Các cột của ma trận ~a~ được đánh số từ ~1~ đến ~n~ từ trái sang phải. Phần tử ở hàng ~i~, cột ~j~ được ký hiệu là ~a_{i,j}~.

Bảng ~a~ được gọi là tương thích với dãy ~t = (t_1, t_2, \ldots, t_n)~ nếu với mọi ~(i, j)~ với ~1 \leq i, j \leq n~:

  • ~a_{i,j} = 0 \leftrightarrow t_i = t_j~.
  • ~a_{i,j} = 1 \leftrightarrow t_i < t_j~.
  • ~a_{i,j} = 2 \leftrightarrow t_i \leq t_j~.
  • ~a_{i,j} = -1 \leftrightarrow t_i > t_j~.
  • ~a_{i,j} = -2 \leftrightarrow t_i \geq t_j~.

Yêu cầu: cho trước ma trận ~a~, hãy tìm dãy số nguyên dương ~t~ tương thích với ~a~, sao cho giá trị lớn nhất của dãy ~t~ là nhỏ nhất có thể. Biết rằng luôn tồn tại một dãy ~t~ như vậy.

Input

  • Dòng ~1~: Số nguyên dương ~n~.
  • ~n~ dòng tiếp theo, mỗi dòng chứa đúng ~n~ số nguyên dương thể hiện ma trận ~a~.

Output

  • Dòng ~1~: Ghi ra số lớn nhất của dãy ~t~.
  • Dòng ~2~: Ghi ra ~n~ số nguyên dương thể hiện dãy ~t~. Nếu có nhiều dãy thỏa mãn có cùng giá trị lớn nhất, bạn được in ra một dãy bất kì.

Giới hạn

  • Trong ~30\%~ số lượng test (trị giá ~30~ điểm): ~n \le 7~
  • Trong ~70\%~ số lượng test còn lại (trị giá ~70~ điểm): ~n \le 77~

Sample Input

3
0 1 1
-1 0 1
-1 -1 0

Sample Output

3
1 2 3

Comments

Please read the guidelines before commenting.


There are no comments at the moment.