1955B.md (2150B)
1 Source: https://codeforces.com/problemset/problem/1955/B 2 3 B. Progressive Square 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 A progressive square of size $n$ is an $n \times n$ matrix. Maxim chooses three integers $a_{1,1}$, $c$, and $d$ and constructs a progressive square according to the following rules: 22 23 $$a_{i+1,j} = a_{i,j} + c$$ 24 25 $$a_{i,j+1} = a_{i,j} + d$$ 26 27 For example, if $n = 3$, $a_{1,1} = 1$, $c=2$, and $d=3$, then the progressive square looks as follows: 28 29 $$ \begin{pmatrix} 1 & 4 & 7 \\ 3 & 6 & 9 \\ 5 & 8 & 11 \end{pmatrix} $$ 30 31 Last month Maxim constructed a progressive square and remembered the values of $n$, $c$, and $d$. Recently, he found an array $b$ of $n^2$ integers in random order and wants to make sure that these elements are the elements of that specific square. 32 33 It can be shown that for any values of $n$, $a_{1,1}$, $c$, and $d$, there exists exactly one progressive square that satisfies all the rules. 34 35 Input 36 37 The first line contains an integer $t$ ($1 \le t \le {10} ^ 4$) — the number of test cases. 38 39 The first line of each test case contains three integers $n$, $c$, and $d$ ($2 \le n \le 500$, $1 \le c, d \le 10^6$) — the size of the square and the values of $c$ and $d$ as described in the statement. 40 41 The second line of each test case contains $n \cdot n$ integers $b_1, b_2, \dots, b_{n \cdot n}$ ($1 \le b_i \le 10^9$) — the elements found by Maxim. 42 43 It is guaranteed that the sum of $n ^ 2$ over all test cases does not exceed $25 \cdot {10} ^ 4$. 44 45 Output 46 47 For each test case, output "YES" in a separate line if a progressive square for the given $n$, $c$, and $d$ can be constructed from the array elements $a$, otherwise output "NO". 48 49 You can output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes", and "YES" will be accepted as a positive answer. 50 51 Example 52 53 Input 54 55 ``` 56 5 57 58 3 2 3 59 60 3 9 6 5 7 1 10 4 8 61 62 3 2 3 63 64 3 9 6 5 7 1 11 4 8 65 66 2 100 100 67 68 400 300 400 500 69 70 3 2 3 71 72 3 9 6 6 5 1 11 4 8 73 74 4 4 4 75 76 15 27 7 19 23 23 11 15 7 3 19 23 11 15 11 15 77 ``` 78 79 Output 80 81 ``` 82 NO 83 YES 84 YES 85 NO 86 NO 87 ```