PROBLEM LINK:
Lockdown Initiated
Setter:Ankita Singh
Tester: Aishik Bhattacharya
DIFFICULTY:
Cakewalk
PREREQUISITE:
Adhoc
EXPLANATION
Since in an n * m grid the farthest cell possible from (0, 0) is (n-1, m-1). So, the position of Brimstone is (n-1, m-1). Brimstone is already standing at the edge of the grid, so the minimum time needed by him to escape is Q seconds. In order to catch Brimstone, Killjoy needs to reach the (n-1, m-1) cell in the shortest possible duration. Shortest distance from (0, 0) to (m-1, n-1) is (m+n-1). Since Killjoy needs to open (m+n-2) doors to reach (n-1, m-1) and he takes 0 seconds in moving from one cell to another. So the minimum time needed by Killjoy to reach Brimstone is ( K* (m+n-2)) seconds.
So the Brimstone will be able to escape the lockdown if and only if Q < ( K * (m+n-2)) and the answer will be YES otherwise he will get caught by Killjoy, the answer will be NO.
Time Complexity: O(1)
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
int t;
cin >> t;
while (t--)
{
ll m, n, k, q;
cin >> n >> m >> k >> q;
ll time = (m+n-2)*k;
if(time <= q)
cout << "NO\n";
else
cout << "YES\n";
}
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
#define int long long
#define double long double
#define fastIO ios_base::sync_with_stdio(false);cin.tie(NULL);
#define endl '\n'
#define Aishik int32_t main ()
using namespace std;
Aishik {
fastIO
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int testcases, test;
//testcases = 1;
cin >> testcases;
assert(testcases <= 1e5);
for (test = 1; test <= testcases; test++) {
int n, m, k, q, sum, maxm, minm, count, flag;
int ans;
cin >> n >> m >> k >> q;
assert(n <= 1e5);
assert(m <= 1e5);
assert(k <= 1e12);
assert(q <= 1e16);
if (q >= k * (n + m - 2)) {
cout << "NO" << endl;
}
else {
cout << "YES" << endl;
}
}
return 0;
}