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  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  98 99 In the third test case, we can color all cells with pigment $1$.