ARYAGRID - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: fremder
Tester: wasd2401
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

Basic math

PROBLEM:

Arya is stuck in an N\times M grid, initially at position (X_0, Y_0), and can only move L units up/down/left/right at a time.
How many distinct cells can be visited?

EXPLANATION:

In a single move, Arya can change one coordinate by L (either an increase or a decrease).
This means that the only cells that can possibly be visited are those of the form
(X_0 + aL, Y_0 + bL), where a and b are integers (possibly negative).

On the other hand, it’s also easy to see that any cell of this form can be visited (as long as it’s within the grid).
So, we just need to count the number of cells of the form (X_0 + aL, Y_0 + bL) that lie within the grid; equivalently, we count the number of valid (a, b) pairs.
That means:

  • 1 \leq X_0 + aL \leq N; and
  • 1 \leq Y_0 + bL \leq M

Let’s look at the first condition.
1 \leq X_0 + aL \leq N means that 1 - X_0 \leq aL \leq N - X_0.
Splitting this into two inequalities, we see that:

  • 1 - X_0 \leq aL, meaning a \geq \frac{1-X_0}{L}.
    Since a must be an integer, this means the minimum allowed value for a is \left\lceil \frac{1-X_0}{L} \right\rceil.
  • aL \leq N - X_0.
    Again, since a must be integral, the maximum allowed value for a is \left\lfloor \frac{N-X_0}{L} \right\rfloor.

Here \left\lfloor \ \ \right\rfloor and \left\lceil \ \ \right\rceil denote the floor and ceiling functions, respectively.

Notice that this gives us a range for a: it must satisfy

\left\lceil \frac{1-X_0}{L} \right\rceil \leq a \leq \left\lfloor \frac{N-X_0}{L} \right\rfloor

Any a within this range is valid, so the answer is just the number of integers in this range, which is easy to calculate (the number of integers in the interval [l, r] is (r-l+1)).
Let this length be S_1.

Similarly, the inequalities on b will give you some range of integers that it can take (the analysis is exactly the same).
Let this length be S_2.

The answer is then simply S_1 \times S_2.

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

CODE:

Author's code (C++) 
#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main() {
	// your code goes here
	int t;
	cin >> t;
	while(t--){
	    int n,m,x,y,l;
	    cin >> n >> m >> x >> y >> l ;
	    int dx = (x-1)/l + (n-x)/l + 1;
	    int dy = (y-1)/l + (m-y)/l + 1;
	    cout << dx*dy << endl;
	}
}
Tester's code (C++) 
/*

*       *  *  ***       *       *****
 *     *   *  *  *     * *        *
  *   *    *  ***     *****       *
   * *     *  * *    *     *   *  *
    *      *  *  *  *       *   **

                                 *
                                * *
                               *****
                              *     *
        *****                *       *
      _*     *_
     | * * * * |                ***
     |_*  _  *_|               *   *
       *     *                 *  
        *****                  *  **
       *     *                  ***
  {===*       *===}
      *  IS   *                 ***
      *  IT   *                *   *
      * RATED?*                *  
      *       *                *  **
      *       *                 ***
       *     *
        *****                  *   *
                               *   *
                               *   *
                               *   *
                                ***   

*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define osl tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
#define ll long long
#define ld long double
#define forl(i, a, b) for(ll i = a; i < b; i++)
#define rofl(i, a, b) for(ll i = a; i > b; i--)
#define fors(i, a, b, c) for(ll i = a; i < b; i += c)
#define fora(x, v) for(auto x : v)
#define vl vector<ll>
#define vb vector<bool>
#define pub push_back
#define pob pop_back
#define fbo find_by_order
#define ook order_of_key
#define yesno(x) cout << ((x) ? "YES" : "NO")
#define all(v) v.begin(), v.end()

const ll N = 2e5 + 4;
const ll mod = 1e9 + 7;
// const ll mod = 998244353;

ll modinverse(ll a) {
	ll m = mod, y = 0, x = 1;
	while (a > 1) {
		ll q = a / m;
		ll t = m;
		m = a % m;
		a = t;
		t = y;
		y = x - q * y;
		x = t;
	}
	if (x < 0) x += mod;
	return x;
}
ll gcd(ll a, ll b) {
	if (b == 0)
		return a;
	return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
	return (a / gcd(a, b)) * b;
}
bool poweroftwo(ll n) {
	return !(n & (n - 1));
}
ll power(ll a, ll b, ll md = mod) {
	ll product = 1;
	a %= md;
	while (b) {
		if (b & 1) product = (product * a) % md;
		a = (a * a) % md;
		b /= 2;
	}
	return product % md;
}
void panipuri() {
	ll n, m = 0, k = -1, c = 0, sum = 0, q = 0, ans = 0, p = 1;
	string s;
	bool ch = true;
	ll x,y;
	cin >> n>>m>>x>>y>>c;
	ll n1=(n+c-1)/c;
	ll m1=(m+c-1)/c;
	x=(x-1)%c+1;
	y=(y-1)%c+1;
	if(x>(n-1)%c+1) n1--;
	if(y>(m-1)%c+1) m1--;
	cout<<n1*m1;
	return;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	#endif
	int laddu = 1;
	cin >> laddu;
	forl(i, 1, laddu + 1) {
		// cout << "Case #" << i << ": ";
		panipuri();
		cout << '\n';
	}
}
Editorialist's code (Python) 
for _ in range(int(input())):
    n, m, x, y, l = map(int, input().split())
    x, y = x%l, y%l
    if x == 0: x = l
    if y == 0: y = l
    # x + kl <= n -> kl <= n - x -> k <= (n-x)/l
    ans = ((n-x)//l + 1) * ((m-y)//l + 1)
    print(ans)
1 Like