RENV20 Editorial | TERM20 | UIET PU Campus Chapter

editorial
, , , ,
1

PROBLEM LINK:

RENOVATION

Setter: Adarsh
Tester: Nitin Pundir
Editorialist: Adarsh

DIFFICULTY

easy

PREREQUISITES

GCD

PROBLEM

Given a rectangle find the largest side of square such that squares with these sides completely fit inside the rectangle.

EXPLANATION

Since we need to reduce the cost of cutting hence we need need to reduce the number of squares which means cut squares with greatest possible side, to find the greatest possible side simply find the greatest common divisor of sides of rectangle.

TIME COMPLEXITY

O(min(length,width)).

SOLUTIONS

Setter's Solution 
#include<bits/stdc++.h>
using namespace std;

long long gcd(long long a,long long b) 
{ 
    if (a == 0) 
        return b; 
    return gcd(b % a, a); 
} 

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        long long len,wid,cost;
        cin>>len>>wid>>cost;
        long long side = gcd(len,wid);
        cout<<side<<" "<<cost*(len*wid)/(side*side)<<endl;

    }
    }
Tester's Solution 
#include<iostream>
#include <vector>
#include <cstdlib>
#include<algorithm>
#include<string>
#include<cmath>
#include<math.h>
#include <list>
#include<bitset>
#define ll long long
using namespace std;
ll md=1000000007;
ll diff=-1;
string mins;


int main()
{
 ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t;
cin>>t;
while(t--)
{
  ll l,b,x;
  cin>>l>>b>>x;
  ll side=__gcd(l,b);
  cout<<side<<" "<<x*l*b/(side*side)<<endl;
}      
return 0;
}
1 Like