RELBOARD - Relative Board
English | Vietnamese |
Given a matrix A with dimension N*N (2 ≤ N ≤ 1000) which contains only 6 types of value: {-1, -2, 0, 1, 2, 3}
A is called the relative board of a sequence T = (T1, T2, ..., Tn), or T relates to A if:
- Aij = 0 : Ti = Tj
- Aij = 1 : Ti < Tj
- Aij = -1 : Ti > Tj
- Aij = 2 : Ti ≤ Tj
- Aij = -2 : Ti ≥ Tj
- Aij = 3 : Ti is not equal to Tj
For all i, j: 1 <= i, j <= N
Given the relative board A, find the sequence of positive integers T = (T1, T2, ..., Tn) that relates to A such that Max(T) is as small as possible. Suppose that the sequence T always exists.
Define Max(T) = Max(T1, T2, ..., Tn).
Input
The first line contains an integer N. N lines follow, each line contains N integers that describe the relative board A.
Output
The first line contains Max(T). The second line contains N separated positive integers T1, T2, .., Tn.
Score
Your score = Max(T).Example
Input: 6 0 1 1 1 2 2 -2 0 1 0 2 2 -2 -1 0 3 0 1 -2 -2 3 0 1 1 -1 -2 0 -1 0 1 -1 -2 -1 -1 -1 0 Output: 4 1 2 3 2 3 4 -> Score = 4
hide comments
Race with time:
2011-02-06 14:19:44
I think it's because there are several test cases and the score is the average of them. |
|
kritivasas:
2011-01-18 16:02:39
can i get one more test case? |
|
Pinco Pallino:
2010-12-30 16:51:59
How is possible that some scores are not integer? |
Added by: | Race with time |
Date: | 2009-04-05 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | Mr. Lê Minh Hoàng |