codeforces-scrape

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

1710A.md (2684B)


      1 Source: https://codeforces.com/problemset/problem/1710/A
      2 
      3 A. Color the Picture
      4 
      5 time limit per test
      6 
      7 1 second
      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 picture can be represented as an $n\times m$ grid ($n$ rows and $m$ columns) so that each of the $n \cdot m$ cells is colored with one color. You have $k$ pigments of different colors. You have a limited amount of each pigment, more precisely you can color at most $a_i$ cells with the $i$-th pigment.
     22 
     23 A picture is considered beautiful if each cell has at least $3$ toroidal neighbors with the same color as itself.
     24 
     25 Two cells are considered toroidal neighbors if they toroidally share an edge. In other words, for some integers $1 \leq x_1,x_2 \leq n$ and $1 \leq y_1,y_2 \leq m$, the cell in the $x_1$-th row and $y_1$-th column is a toroidal neighbor of the cell in the $x_2$-th row and $y_2$-th column if one of following two conditions holds:
     26 
     27 * $x_1-x_2 \equiv \pm1 \pmod{n}$ and $y_1=y_2$, or
     28 * $y_1-y_2 \equiv \pm1 \pmod{m}$ and $x_1=x_2$.
     29 
     30 Notice that each cell has exactly $4$ toroidal neighbors. For example, if $n=3$ and $m=4$, the toroidal neighbors of the cell $(1, 2)$ (the cell on the first row and second column) are: $(3, 2)$, $(2, 2)$, $(1, 3)$, $(1, 1)$. They are shown in gray on the image below:
     31 
     32  ![](https://espresso.codeforces.com/cf2cdf05dcea672dd280a963ac1e48a6119792f7.png) The gray cells show toroidal neighbors of $(1, 2)$. 
     33 
     34 Is it possible to color all cells with the pigments provided and create a beautiful picture?
     35 
     36 Input
     37 
     38 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 10^4$). The description of the test cases follows.
     39 
     40 The first line of each test case contains three integers $n$, $m$, and $k$ ($3 \leq n,m \leq 10^9$, $1 \leq k \leq 10^5$) — the number of rows and columns of the picture and the number of pigments.
     41 
     42 The next line contains $k$ integers $a_1,a_2,\dots, a_k$ ($1 \leq a_i \leq 10^9$) — $a_i$ is the maximum number of cells that can be colored with the $i$-th pigment.
     43 
     44 It is guaranteed that the sum of $k$ over all test cases does not exceed $10^5$.
     45 
     46 Output
     47 
     48 For each test case, print "Yes" (without quotes) if it is possible to color a beautiful picture. Otherwise, print "No" (without quotes).
     49 
     50 Example
     51 
     52 Input
     53 
     54 ```
     55 6
     56 
     57 4 6 3
     58 
     59 12 9 8
     60 
     61 3 3 2
     62 
     63 8 8
     64 
     65 3 3 2
     66 
     67 9 5
     68 
     69 4 5 2
     70 
     71 10 11
     72 
     73 5 4 2
     74 
     75 9 11
     76 
     77 10 10 3
     78 
     79 11 45 14
     80 ```
     81 
     82 Output
     83 
     84 ```
     85 Yes
     86 No
     87 Yes
     88 Yes
     89 No
     90 No
     91 ```
     92 
     93 Note
     94 
     95 In the first test case, one possible solution is as follows:
     96 
     97  ![](https://espresso.codeforces.com/b21aec46170ebcd9c1ccbde8910917c2c36c8b61.png) 
     98 
     99 In the third test case, we can color all cells with pigment $1$.