2101A.md (2126B)
1 Source: https://codeforces.com/problemset/problem/2101/A 2 3 A. Mex in the Grid 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given $n^2$ cards with values from $0$ to $n^2-1$. You are to arrange them in a $n$ by $n$ grid such that there is exactly one card in each cell. 22 23 The MEX (minimum excluded value) of a subgrid$^{\text{∗}}$ is defined as the smallest non-negative integer that does not appear in the subgrid. 24 25 Your task is to arrange the cards such that the sum of MEX values over all $\left(\frac{n(n+1)}{2}\right)^2$ subgrids is maximized. 26 27 $^{\text{∗}}$A subgrid of a $n$ by $n$ grid is specified by four numbers $l_1, r_1, l_2, r_2$ satisfying $1\le l_1\le r_1\le n$ and $1\le l_2\le r_2\le n$. The element in the $i$-th row and the $j$-th column of the grid is part of the subgrid if and only if $l_1\le i\le r_1$ and $l_2\le j\le r_2$. 28 29 Input 30 31 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). The description of the test cases follows. 32 33 The first line of each test case contains a single integer $n$ ($1\le n\le 500$) — the side length of the grid. 34 35 It is guaranteed that the sum of $n$ over all test cases does not exceed $1000$. 36 37 Output 38 39 For each test case, output $n$ lines, each containing $n$ integers representing the elements of the grid. 40 41 If there are multiple answers, you can output any of them. 42 43 Example 44 45 Input 46 47 ``` 48 2 49 50 2 51 52 3 53 ``` 54 55 Output 56 57 ``` 58 0 1 59 2 3 60 8 4 5 61 6 0 1 62 7 2 3 63 ``` 64 65 Note 66 67 In the first test case, one valid arrangement is: 68 69 | | | 70 | --- | --- | 71 | 0 | 1 | 72 | 2 | 3 | 73 74 There are $9$ subgrids in total, and the $4$ of them with non-zero MEX are shown below: 75 76 | | 77 | --- | 78 | 0 | 79 80 values:$[0]$ — MEX: $1$ 81 82 | | | 83 | --- | --- | 84 | 0 | 1 | 85 86 values:$[0, 1]$ — MEX: $2$ 87 88 | | 89 | --- | 90 | 0 | 91 | 2 | 92 93 values:$[0, 2]$ — MEX: $1$ 94 95 | | | 96 | --- | --- | 97 | 0 | 1 | 98 | 2 | 3 | 99 100 values:$[0, 1, 2, 3]$ — MEX: $4$ 101 102 The sum of MEX over all subgrids would be $1+2+1+4 = 8$. It can be proven that no other arrangements have a larger sum of MEX values.