Metric Matrices

Interview

Time limit1sMemory limit1024 MB

Summary

Given an N by N distance matrix, check the four metric axioms and print the smallest number of any axiom it violates, or 0 if it is a metric.

Level: Easy3 of 10
Topics: Brute force, Matrix, Implementation
Solved: No attempts yet

Problem

Given a square distance matrix, where a[i,j] is the distance between point i and point j, determine whether the distance matrix is a metric.

A distance matrix a[x,y] is a metric if and only if

$f(x,x) = 0$
$f(x,y) > 0$ if $x \neq y$
$f(x,y) = f(y,x)$
$f(x,y) + f(y,z) \geq f(x,z)$

Input

The first line contains one integer N, the number of rows and columns, with $2 \leq N \leq 30$ .

The next N lines each contain N space-separated integers, and each integer is between -32000 and 32000 inclusive. The first of these lines is the first row, and the first number in each line is the first column.

Output

Print a single line with a single digit: the smallest digit among the facts below that holds.

0: The matrix is a metric.
1: The matrix is not a metric because it violates rule 1.
2: The matrix is not a metric because it violates rule 2.
3: The matrix is not a metric because it violates rule 3.
4: The matrix is not a metric because it violates rule 4.

Examples1

Example 1
Input
```
4
0 1 2 3
1 0 1 2
2 1 0 1
3 2 1 0
```
Expected output
```
0
```