← 返回题目列表

Codeforces · 1938/E

E. 重复项

中文机器翻译题面 查看原题

以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。

Duplicates - 原题 PDF 第 1 页
原题PDF第9页
Duplicates - 原题 PDF 第 2 页
原题PDF第10页
可复制的 PDF 提取文本
Problem E
                        Duplicates
                     Time limit: 2 seconds


We say that a number sequence contains duplicates if there is an element that appears more than once in the sequence.
Formally, a sequence (a1, . . . , an) contains duplicates if there exist two indices i and j such that i ̸= j and ai = aj.

You are given an n × n matrix X. Each entry in X is an integer between 1 and n, inclusive. You can modify zero
or more entries in X to arbitrary integers between 1 and n, inclusive. Different entries can be modified to different
integers.

Your task is to make modifications to entries of X such that all of the following hold:


     • For each row i, the sequence (Xi1, Xi2, ..., Xin) contains duplicates.

     • For each column j, the sequence (X1j, X2j, ..., Xnj) contains duplicates.


Compute the minimum number of entries that need to be modified to achieve this. Also, find one possible set of
modifications to do it. For each modification, you have to specify which entry will be modified and to what value.
Note that the minimum number of entries to be modified can be zero when the given matrix X already satisfies the
conditions above.

Input

The first line of input contains one integer t (1 ≤t ≤1000) representing the number of test cases. After that, t test
cases follow. Each of them is presented as follows.

The first line of a test case contains one integer n (3 ≤n ≤100). Each of the next n lines contains n integers. The
j-th integer in the i-th line denotes Xij (1 ≤Xij ≤n).
The sum of n2 across all test cases in one input file does not exceed 10 000.

Output

For each test case, output a set of modifications in the following format.

On the first line, output an integer m representing the minimum number of entries that need to be modified. On each
of the next m lines, output three integers i, j, and v. This represents a single modification where the entry Xij will be
modified to v. All of the three integers must be between 1 and n, inclusive.

If there are multiple solutions, you can output any of them.





ICPC Asia Pacific Championship 2024 Problem E: Duplicates

Sample Input #1                          Sample Output #1
 5                                      2
 4                                      2 1 1
 3 2 1 1                                4 2 3
 2 1 3 4                                3
 1 3 3 1                                2 1 3
 4 4 4 2                                2 2 3
 3                                      3 3 3
 1 3 1                                  0
 2 1 3                                  1
 3 2 2                                  1 2 2
 5                                      1
 1 1 1 1 1                              2 1 1
 1 1 1 1 1
 1 1 1 1 1
 1 1 1 1 1
 1 1 1 1 1
 3
 1 1 2
 2 2 1
 2 3 2
 3
 1 1 3
 3 2 1
 3 1 3


Explanation for the sample input/output #1

In the first test case, the matrix after the modification is as follows.

                               13  12  13  14
                                          1  3  3  1                                                                                            4  3  4  2





ICPC Asia Pacific Championship 2024 Problem E: Duplicates