原题链接：

Problem - 1710A - Codeforces (Unofficial mirror by Menci)

题目描述：

A picture can be represented as an n×mn×m grid (nn rows and mm columns) so that each of the n⋅mn⋅m cells is colored with one color. You have kk pigments of different colors. You have a limited amount of each pigment, more precisely you can color at most aiai cells with the ii-th pigment.

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≤x1,x2≤n1≤x1,x2≤n and 1≤y1,y2≤m1≤y1,y2≤m, the cell in the x1x1-th row and y1y1-th column is a toroidal neighbor of the cell in the x2x2-th row and y2y2-th column if one of following two conditions holds:

• x1−x2≡±1(modn)x1−x2≡±1(modn) and y1=y2y1=y2, or
• y1−y2≡±1(modm)y1−y2≡±1(modm) and x1=x2x1=x2.

Notice that each cell has exactly 44 toroidal neighbors. For example, if n=3n=3 and m=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?

Input

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

The first line of each test case contains three integers nn, mm, and kk (3≤n,m≤1093≤n,m≤109, 1≤k≤1051≤k≤105) — the number of rows and columns of the picture and the number of pigments.

The next line contains kk integers a1,a2,…,aka1,a2,…,ak (1≤ai≤1091≤ai≤109) — aiai is the maximum number of cells that can be colored with the ii-th pigment.

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

Output

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

题目大意：

给定一个n行m列的空白矩阵，这个矩阵是四周成环的，然后给定k种染料，每种染料数量有ai个（可以涂ai个单元格），问有没有一种染色方式，可以让这个矩阵的每一个单元格都至少有三个同色的相邻单元格。

解题思路：

在纸上画一下会发现，要达成题目的要求最佳的方式是每种颜色涂满两行以上或者两列以上。（整行、整列）

先考虑按行涂色，先把每种颜色的数量从大到小排序，如果矩阵行数为偶数，则我们只需要检查每种颜色是否都能够涂两行以上，

并将每种颜色能涂满的行数进行累加，一旦有任何一种颜色无法涂满两整行，并且此时则累加和并未超过n行，则无解。

直到最后如果总和超过了n行，则有解。

如果矩阵行数为奇数，则至少要有一种颜色能涂三行及以上。

按列涂色方式同理。

代码（CPP）：

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
typedef unsigned long long ull;
const int maxn = 1e5 + 10;
const int INF = 0x3fffffff;
int n, m, k, a[maxn];

bool check(int n, int m)
{
    int sum = 0;
    for (int i = 1; i <= k; i++)
    {
        int t = a[i] / m;
        if((n & 1) && i == 1 && t < 3)
            break;
        if(t < 2)
            break;
        sum += t;
        if(sum >= n)
            break;
    }
    return sum >= n;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed;
    cout.precision(18);

    int t;
    cin >> t;
    while(t--)
    {
        cin >> n >> m >> k;
        for (int i = 1; i <= k; i++)
        {
            cin >> a[i];
        }
        sort(a + 1, a + 1 + k, greater<int>());
        if(check(n, m))
        {
            cout << "Yes\n";
            continue;
        }
        swap(n, m);
        if(check(n, m))
        {
            cout << "Yes\n";
            continue;
        }
        cout << "No\n";
    }
    return 0;
}