#P13048. [GCJ 2020 Qualification] Vestigium

    ID: 12853 Type: RemoteJudge 20000ms 1024MiB Tried: 0 Accepted: 0 Difficulty: 2 Uploaded By: Tags>模拟2020排序Google Code Jam

[GCJ 2020 Qualification] Vestigium

题目描述

Vestigium means "trace" in Latin. In this problem we work with Latin squares and matrix traces.

The trace of a square matrix is the sum of the values on the main diagonal (which runs from the upper left to the lower right).

An NN-by-NN square matrix is a Latin square if each cell contains one of NN different values, and no value is repeated within a row or a column. In this problem, we will deal only with "natural Latin squares" in which the NN values are the integers between 1 and NN.

Given a matrix that contains only integers between 1 and NN, we want to compute its trace and check whether it is a natural Latin square. To give some additional information, instead of simply telling us whether the matrix is a natural Latin square or not, please compute the number of rows and the number of columns that contain repeated values.

输入格式

The first line of the input gives the number of test cases, TT. TT test cases follow. Each starts with a line containing a single integer NN: the size of the matrix to explore. Then, NN lines follow. The ii-th of these lines contains NN integers Mi,1M_{i,1}, Mi,2M_{i,2}, \dots, Mi,NM_{i,N}. Mi,jM_{i,j} is the integer in the ii-th row and jj-th column of the matrix.

输出格式

For each test case, output one line containing Case #x: k r c, where xx is the test case number (starting from 1), kk is the trace of the matrix, rr is the number of rows of the matrix that contain repeated elements, and cc is the number of columns of the matrix that contain repeated elements.

3
4
1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1
4
2 2 2 2
2 3 2 3
2 2 2 3
2 2 2 2
3
2 1 3
1 3 2
1 2 3
Case #1: 4 0 0
Case #2: 9 4 4
Case #3: 8 0 2

提示

Sample Explanation

In Sample Case #1, the input is a natural Latin square, which means no row or column has repeated elements. All four values in the main diagonal are 1, and so the trace (their sum) is 4.

In Sample Case #2, all rows and columns have repeated elements. Notice that each row or column with repeated elements is counted only once regardless of the number of elements that are repeated or how often they are repeated within the row or column. In addition, notice that some integers in the range 1 through NN may be absent from the input.

In Sample Case #3, the leftmost and rightmost columns have repeated elements.

Limits

Test set 1 (7 Pts, Visible Verdict)

  • 1T100.1 \leq T \leq 100.
  • 2N100.2 \leq N \leq 100.
  • 1Mi,jN,1 \leq M_{i,j} \leq N, for all i,j.i, j.