Predict Outcome of the Game
Created by LXC on Tue May 9 10:44:46 2023
https://codeforces.com/problemset/problem/451/C
ranting: 1700
tag: brute force, implementation, math
题意
有三只球队举行比赛
共计n场比赛，每场比赛选两支队伍参与，必有一方会胜利。
现在已经进行了k场比赛，已知第一二支队伍的胜场之差的绝对值为d1，第二三支队伍的胜场之差的绝对值为d2
问能否存在一种可能，在n场比赛后每支队伍的胜场一样。
题解
设k场比赛后三支队伍的胜场分别是x,y,z
那么有:
x+y+z = k
|x-y| = d1
|y-z| = d2
取绝对值后形成4个三元一次方程。
分别解出x,y,z。
只要满足0<=x<=n/3,0<=y<=n/3,0<=z<=n/3即可。
代码
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
|
#include <bits/stdc++.h>
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;
ll n, k, d1, d2;
bool check(ll x, ll y, ll z) {
return (x % 3 == 0 && y % 3 == 0 && z % 3 == 0 && 0 <= x / 3 &&
0 <= y / 3 && 0 <= z / 3 && x / 3 <= n / 3 && y / 3 <= n / 3 &&
z / 3 <= n / 3);
}
void sol() {
cin >> n >> k >> d1 >> d2;
if (n % 3) {
cout << "no\n";
return;
}
ll x1 = k + 2 * d1 + d2, y1 = k - d1 + d2, z1 = k - d1 - 2 * d2;
ll x2 = k - 2 * d1 + d2, y2 = k + d1 + d2, z2 = k + d1 - 2 * d2;
ll x3 = k + 2 * d1 - d2, y3 = k - d1 - d2, z3 = k - d1 + 2 * d2;
ll x4 = k - 2 * d1 - d2, y4 = k + d1 - d2, z4 = k + d1 + 2 * d2;
cout << ((check(x1, y1, z1) || check(x2, y2, z2) || check(x3, y3, z3) ||
check(x4, y4, z4))
? "yes\n"
: "no\n");
}
int main() {
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;
}
|