Domino (easy version)

发表于 分类于 ，

    给你 $t$ 组数据。对于每组数据给你一个 $n \times m$ 的网格（$n$ 为网格高度，$m$ 为网格宽度，且网格的数量为偶数），要求在网格中放置多米诺骨牌，每个骨牌占据 $1\times2$ 的网格区域。对于这 $\frac{nm}{2}$ 个骨牌，要求正好有 $k$ 个横着放置，而剩下的 $\frac{nm}{2}-k$ 个竖着放置，正好铺满台面。现在要你给出对于每组 $n$, $m$ 和 $k$，是否有一种方案满足条件。如果有，输出 YES，反之输出 NO。

Domino (easy version)

Created by LXC on Fri Mar 8 16:03:22 2024

https://codeforces.com/problemset/problem/1551/D1

ranting: 1700

tag: constructive algorithms, math

problem

给你 $t$ 组数据。对于每组数据给你一个 $n \times m$ 的网格（$n$ 为网格高度，$m$ 为网格宽度，且网格的数量为偶数），要求在网格中放置多米诺骨牌，每个骨牌占据 $1\times2$ 的网格区域。对于这 $\frac{nm}{2}$ 个骨牌，要求正好有 $k$ 个横着放置，而剩下的 $\frac{nm}{2}-k$ 个竖着放置，正好铺满台面。现在要你给出对于每组 $n$, $m$ 和 $k$，是否有一种方案满足条件。如果有，输出 YES，反之输出 NO。

solution

对于n为奇数，m为奇数，没有答案。

对于n为奇数，m为偶数，至少有一行要为水平放置，所以$m/2 \le k \le m/2*n$且$k-m/2$为偶数。

对于n为偶数，至多有$\lfloor \frac{m}{2} \rfloor n$个水平块，且$k$为偶数。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

void sol() {
    int n, m, k;
    cin >> n >> m >> k;
    if (n%2) {
        if (m%2) {
            cout << "NO\n";
        } else {
            cout << ((m/2 <= k && k <= m/2*n && 0==(k-m/2)%2)?"YES\n":"NO\n");
        }
    } else {
        cout << ((k <= m/2*n && 0==k%2)?"YES\n":"NO\n");
    }
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}