ZACKHAN - Editorial

Problem Link:

Contest

Practice

Author: Hiral Saini

Tester: Shivani Srivastava

Editorialist: Hiral Saini

Difficulty:

Easy

PREREQUISITES:

GCD

PROBLEM:

We are given the length and the breadth of rectangular shaped cloth out of which, we are required to cut square shaped handkerchieves. The task is to compute the maximum side length of the square shaped handkerchieves.

QUICK EXPLANATION:

The maximum side length can be calculated by computing the GCD of the given length(L) and breadth(B).

EXPLANATION:

We have to find the maximum number of square-shaped handkerchiefs of maximum size possible out of a given cloth material. Here, L and B are the length and breadth of the given cloth material respectively. Now, we have to divide it in square-shaped divisions such that these are the maximum size possible per piece. Which, in this case, will be calculated by finding the Greatest Common Divisor (GCD) of L and B of the given piece of cloth.
For Example,
For a piece of cloth of L= 30 and B=40, the size of maximum square-shaped handkerchiefs possible can be found out by calculating the GCD of its length and breadth which is 10. So, the maximum length of square-shaped handkerchiefs possible is 10 units.

AUTHOR’S AND TESTER’S SOLUTIONS:

The solution can be found here

#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
while(n–)
{
int l,b;
cin>>l>>b;
cout<<__gcd(l,b)<<endl;
}
}

#include
using namespace std;
void hcf(int a, int b) // a<=b
{
int r,q,m;

do{
m = a; // to store the last non-zero value of r
r = b%a;
q = b/a;
b = a;
a = r;

}while(r!=0);

cout<<m;

// else hcf(r,a);
//return 0;
}
int main()
{
cout<<"hcf of 10 and 15 = ";
hcf(10,15);
}

why is 3030 not the max side square in 4030 rectangle?

2 Likes

l=int(input(‘Enter Length:’))
b=int(input(‘Enter Breadth:’))
def hcf(num1,num2):
x=1
min=num1
if num2<min:
min=num2
for i in range(1,int(min/2)+1):
if (num1%i==0 and num2%i==0):
x=i

return x

print(hcf(l,b))

Same question why isn’t 30 the answer or more specifically min(l,b)

Why is min(l,b) the answer? It is not given how many handkerchief we need why not 30 by 30 out of 30 by 40 rectangle is possible?

You have to use the whole rectangle.

You have to use the whole rectangular cloth.

@akram01
40, 30 - 1200 sq units
i could get a 3 squares of length 20 each

Yes, but you are not using the entire rectangular cloth. Draw the rough rectangle of length 40 and breadth 30 and try to make the 3 squares of length 20. You will see that you are not fully using the breadth part.

2 Likes

what’s wrong with below code?
// C++ program for linked list implementation of stack
#include <bits/stdc++.h>
#include // for lower_bound, upper_bound and sort
#include
#include // for vector
using namespace std;

int gcd(int a, int b)
{
return b == 0 ? a : gcd(b, a % b);
}
// Driver code
int main()
{
int t;
cin>>t;
while(t–){
int l,b;
cin>>l>>b;

    cout<<gcd(l,b);

}
return 0;
}