codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1520C.md (1243B)


      1 Source: https://codeforces.com/problemset/problem/1520/C
      2 
      3 C. Not Adjacent Matrix
      4 
      5 time limit per test
      6 
      7 4 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 We will consider the numbers $a$ and $b$ as adjacent if they differ by exactly one, that is, $|a-b|=1$.
     22 
     23 We will consider cells of a square matrix $n \times n$ as adjacent if they have a common side, that is, for cell $(r, c)$ cells $(r, c-1)$, $(r, c+1)$, $(r-1, c)$ and $(r+1, c)$ are adjacent to it.
     24 
     25 For a given number $n$, construct a square matrix $n \times n$ such that:
     26 
     27 * Each integer from $1$ to $n^2$ occurs in this matrix exactly once;
     28 * If $(r_1, c_1)$ and $(r_2, c_2)$ are adjacent cells, then the numbers written in them must not be adjacent.
     29 
     30 Input
     31 
     32 The first line contains one integer $t$ ($1 \le t \le 100$). Then $t$ test cases follow.
     33 
     34 Each test case is characterized by one integer $n$ ($1 \le n \le 100$).
     35 
     36 Output
     37 
     38 For each test case, output:
     39 
     40 * -1, if the required matrix does not exist;
     41 * the required matrix, otherwise (any such matrix if many of them exist).
     42 
     43 The matrix should be outputted as $n$ lines, where each line contains $n$ integers.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 3
     51 1
     52 2
     53 3
     54 ```
     55 
     56 Output
     57 
     58 ```
     59 1
     60 -1
     61 2 9 7
     62 4 6 3
     63 1 8 5
     64 ```