[Solution] Color the Picture solution codeforces

Color the Picture solution codeforces – A picture can be represented as an 𝑛×𝑚n×m grid (𝑛n rows and 𝑚m columns) so that each of the 𝑛𝑚n⋅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 𝑎𝑖ai cells with the 𝑖i-th pigment.

Table of Contents

[Solution] Color the Picture solution codeforces

A picture is considered beautiful if each cell has at least 33 toroidal neighbors with the same color as itself.

Two cells are considered toroidal neighbors if they toroidally share an edge. In other words, for some integers 1𝑥1,𝑥2𝑛1≤x1,x2≤n and 1𝑦1,𝑦2𝑚1≤y1,y2≤m, the cell in the 𝑥1x1-th row and 𝑦1y1-th column is a toroidal neighbor of the cell in the 𝑥2x2-th row and 𝑦2y2-th column if one of following two conditions holds:

  • 𝑥1𝑥2±1(mod𝑛)x1−x2≡±1(modn) and 𝑦1=𝑦2y1=y2, or
  • 𝑦1𝑦2±1(mod𝑚)y1−y2≡±1(modm) and 𝑥1=𝑥2x1=x2.

Notice that each cell has exactly 44 toroidal neighbors. For example, if 𝑛=3n=3 and 𝑚=4m=4, the toroidal neighbors of the cell (1,2)(1,2) (the cell on the first row and second column) are: (3,2)(3,2)(2,2)(2,2)(1,3)(1,3)(1,1)(1,1). They are shown in gray on the image below:

The gray cells show toroidal neighbors of (1,2)(1,2).
Is it possible to color all cells with the pigments provided and create a beautiful picture?

[Solution] Color the Picture solution codeforces

Each test contains multiple test cases. The first line contains the number of test cases 𝑡t (1𝑡1041≤t≤104). The description of the test cases follows.

The first line of each test case contains three integers 𝑛n𝑚m, and 𝑘k (3𝑛,𝑚1093≤n,m≤1091𝑘1051≤k≤105) — the number of rows and columns of the picture and the number of pigments.

The next line contains 𝑘k integers 𝑎1,𝑎2,,𝑎𝑘a1,a2,…,ak (1𝑎𝑖1091≤ai≤109) — 𝑎𝑖ai is the maximum number of cells that can be colored with the 𝑖i-th pigment.

It is guaranteed that the sum of 𝑘k over all test cases does not exceed 105105.


For each test case, print “Yes” (without quotes) if it is possible to color a beautiful picture. Otherwise, print “No” (without quotes).

[Solution] Color the Picture solution codeforces


4 6 3
12 9 8
3 3 2
8 8
3 3 2
9 5
4 5 2
10 11
5 4 2
9 11
10 10 3
11 45 14

[Solution] Color the Picture solution codeforces



In the first test case, one possible solution is as follows:

In the third test case, we can color all cells with pigment 11.


For Solution

Click Here

Leave a Comment