VMREL6 - Bảng quan hệ
Giới hạn- Thời gian: 1.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Cho một ma trận A kích thước N*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 nếu:
- Dãy T gồm đúng N phần tử. Các phần tử của dãy T được đánh số từ 1 đến N. Phần tử thứ i được ký hiệu là T(i).
- Với mọi i, j mà 1 ≤ i, j ≤ N:
- A(i,j) = 0 ↔ T(i) = T(j).
- A(i,j) = 1 ↔ T(i) < T(j).
- A(i,j) = 2 ↔ T(i) ≤ T(j).
- A(i,j) = -1 ↔ T(i) > T(j)
- A(i,j) = -2 ↔ T(i) ≥ 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.
Giới hạn
- Trong 30% số lượng test (trị giá 30 điểm): N <= 7
- Trong 70% số lượng test còn lại (trị giá 70 điểm): N <= 77
Example
Input: 3 0 1 1 -1 0 1 -1 -1 0
Output: 3 1 2 3
- Người up: voj
- Nguồn bài: RR