codeforces-scrape

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

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 ```