考虑差分,如果 \(t-1\) 时刻经过 \((x,y)\) 的史莱姆个数等于 \(t\) 时刻经过 \((x,y)\) 的史莱姆个数,答案为 NO
,否则为 YES
。
发现两只史莱姆一定不会相遇,并且若 \(k\) 只史莱姆经过了 \((a,b)\),则有 \(\left\lceil\frac{k}{2}\right\rceil\) 只史莱姆经过 \((a,b+1)\),有 \(\left\lfloor\frac{k}{2}\right\rfloor\) 只史莱姆经过 \((a+1,b)\)。
递推一下即可,时间复杂度 \(O(Tn^2)\),其中 \(n = 120\)。
code
/*
p_b_p_b txdy
AThousandSuns txdy
Wu_Ren txdy
Appleblue17 txdy
*/
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 125;
ll f[maxn][maxn];
inline ll calc(ll t, ll x, ll y) {
if (t < x + y) {
return 0;
}
mems(f, 0);
f[0][0] = t - x - y + 1;
for (int i = 0; i <= x; ++i) {
for (int j = 0; j <= y; ++j) {
f[i + 1][j] += f[i][j] / 2;
f[i][j + 1] += (f[i][j] + 1) / 2;
}
}
return f[x][y];
}
void solve() {
ll t, x, y;
scanf("%lld%lld%lld", &t, &x, &y);
puts(calc(t - 1, x, y) == calc(t, x, y) ? "NO" : "YES");
}
int main() {
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}