Rectangular Game Solution

Problem

You are given an infinite 2d grid with the bottom left cell referenced as (1,1). All the cells contain a value of zero initially. Let’s play a game?

The game consists of N steps wherein each step you are given two integers a and b. The value of each of the cells in the coordinate (u, v) satisfying 1 ≤ u ≤ a and 1 ≤ v ≤ b, is increased by 1. After N such steps, if X is the largest number amongst all the cells in the rectangular board, can you print the number of X‘s in the board?

Hackerrank Problem Link

Input

The first line of input contains a single integer N. N lines follow.
Each line contains two integers a and b separated by a single space.

Output

Output a single integer – the number of X’s.

Constraints

  • 1 ≤ N ≤ 100
  • 1 ≤ a ≤ 106
  • 1 ≤ b ≤ 106

Sample Input

3
2 3
3 7
4 1

Sample Output

2

Solution

//
//  main.cpp
//  Rectangular Game
//
//  Created by Himanshu on 16/02/22.
//

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#define MAX_SIZE 1000001
using namespace std;

int main() {
    int n;
    long long ans, a = MAX_SIZE, b = MAX_SIZE, r, c;
    
    cin>>n;
    while (n--) {
        cin>>r>>c;

        //cells with maximum value will be from 1 to the least of a (and b)
        a = min(a, r);
        b = min(b, c);
    }
    
    ans = a*b;
    cout<<ans;
    
    return 0;
}

Time Complexity: O(1)

Leave a Reply

Your email address will not be published.