REC19A - Editorial


Lockdown Initiated

Setter:Ankita Singh

Tester: Aishik Bhattacharya






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";
            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 {
    #ifndef ONLINE_JUDGE 
        freopen("input.txt", "r", stdin); 
        freopen("output.txt", "w", stdout); 
    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;