PONGAL1 - Editorial

meenaksshi · February 6, 2022, 11:32am

PROBLEM LINK:

Practice
Contest: CTWJ2022 – [Come to Win the Coding Jallikattu]

DIFFICULTY:

CAKEWALK

PREREQUISITES:

Greedy, Math, Ad-hoc, Implementation

PROBLEM:

Find the maximum number of rectangles of size (p x q) that can fit into a rectangle of size (l x b). No two rectangles can overlap. The rectangles can be placed Horizontally or Vertically, but all the rectangles must be placed in the same alignment. (i.e, there shouldn’t be a case where a few rectangles are placed Horizontally and a few others are placed Vertically).

QUICK EXPLANATION:

There are only two possible ways to place all the rectangles.

Place them all Horizontally
Place them all Vertically

Hence, we just need to find the maximum of these two and print the answer.

EXPLANATION:

Code:

    #include "bits/stdc++.h"
    
    using namespace std;
    
    int main()
    {
        int t;
        cin>>t;
        while(t--)
        {
            long long int n, m, a, b, ans;
            cin >> n >> m >> a >> b;
            ans = max((n / a ) * ( m / b), (m / a) * (n / b));
            cout << ans << endl; 
        }
        return 0;
    }

\textbf{Case 1}: Find the number of rectangles that can be placed Horizontally – Divide the total length by length of each rectangle and also divide the total breadth by the breadth of each rectangle. Find their product.

\textbf{Case 2}: Similarly, find the number of rectangles that can be placed if all are aligned Vertically – Divide the total length by the breadth of each rectangle, and divide the total breadth by the length of each rectangle. Multiply them.

The maximum of these two results will be the max number of rectangles that can be placed.

\textbf{Note}:

Floating point division should not be done here – the rectangles must be placed as a whole. A portion of it shouldn’t be cut, hence we are performing Floor division ( For Integer division - // in python and floor function in c++).
The answer might not fit into 32-bit integer. So, use 64-bit datatype like “long long int” to prevent overflow.

SOLUTIONS:

Setter's Solution

    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const ll MOD = 1e9+7;
    #define rep(i,a,b) for(ll i=a;i<b;++i) 
    #define pii pair<ll,ll>
    #define all(x) x.begin(),x.end()
    #define ff first
    #define ss second
    
    int main()
    {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        int tt=1;
        cin>>tt;
        while(tt--)
        {
            ll l,b,p,q;
            cin>>l>>b>>p>>q;
            cout<<max((l/p)*(b/q),(b/p)*(l/q))<<"\n";
        }
    }

Tester's Solution

    for _ in range(int(input())):
        p,q,l,b=map(int,input().split())
        print(max(((p//l)*(q//b)),((p//b)*(q//l))))

Editorialist's Solution

    #include "bits/stdc++.h"
    
    using namespace std;
    
    int main()
    {
        int t;
        cin>>t;
        while(t--)
        {
            long long int n, m, a, b, ans;
            cin >> n >> m >> a >> b;
            ans = max((n / a ) * ( m / b), (m / a) * (n / b));
            cout << ans << endl; 
        }
        return 0;
    }