Captain and Shield

help
,
1

Captain America is searching for a new shield to fight with the Thanos . This time he wants a Rectangular Shield. He can hold the rectangular shield of the width, not greater than w and height, not greater than h . Captain wants a special Shield. A special Shield is that whose ratio of width to the height is equal to the ratio of x to the y .

There can be many Special shields and The Captain wants to try every Special Shield with the width a (a ≤ w) and the height b (b ≤ h) and ratio of a to the b equal to the ratio of x to the y .

You have to determine the number of special shields that the captain can try.

Two Shields are said to be different if they have different shield width or different shield height.

Input Format

The first line contains four integers w , h , x , y .

Constraints

1 ≤ w , h , x , y ≤ 10^18

( NOTE : You need to take long long int data type to store these values for C/C++ users)

Output Format

Print one integer — the number of different special shields that meets the aforementioned constraints.

Sample Input 0

17 15 5 3

Sample Output 0

3

Explanation 0

There are 3 possible Shields with width a and height b (5,3), (10,6), (15,9). In all these 3 shields their ratio of width and height is equal to 5 is to 3 (i.e. x is to y).

Sample Input 1

14 16 7 22

Sample Output 1

0

Actually, this question is from the private contest of a college in our city, I m not able to find out logic I got the partial score, can anyone help?
@I_returns @andrew234
@anon55659401 @gagangaur @marksman

2

x = x/GCD(x,y);
y = y/GCD(x,y);
and then
min( floor(w/x), floor(h/y) )
will this work?

3

@anon33414303 Some test case not passes

4

one thing you can do is traverse the multiples of x and y till the values are less than min(w,h) or the ratio of those multiple is equal to the ratio of x and y and thus increment the count it would take approx O(n)
ex-
given x and y are 5 , 3
given w and h are 17 , 15

5 10 15 (since next multiple will exceed the value of the w so break here)
3 6 9
hope it helped and please do tell if you find something better than this .:slightly_smiling_face:

5

O(n) will not pass. i tried already.

6

Hi, Please share the link of the problem.

7

@marksman bro the full problem is described , u tell me the approach , if u can :slight_smile:

8

x = x/GCD(x,y);
y = y/GCD(x,y);
and then
min( floor(w/x), floor(h/y) )
will this work?

9

No , this will also give wrong answer to many cases.

11

https://www.hackerrank.com/contests/procode-final-round-avengers-theme/challenges/captains-shield-1/submissions/code/1314563255

@marksman @anon33414303 @gagangaur

12

This got AC.
g=__gcd(x,y);
x/=g;
y/=g;
ans=min(w/x,h/y);

13

Still not passes fully got 54 points out of 100

15

Bro i give the link in above comment , u can submit and tell after u got full marks.

16

I have already submitted and got full marks.
https://www.hackerrank.com/contests/procode-final-round-avengers-theme/challenges/captains-shield-1/submissions

17

Then Please share ur full code bcz i applied everything :(:sleepy:

18 
#include<bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
int gcd(int a,int b){if (a==0)return b;return gcd(b%a,a);}

signed main()
{
	int w,x,h,y,g,c=0;
	cin>>w>>h>>x>>y;
	g=__gcd(x,y);
	x/=g;
	y/=g;
	c=min(w/x,h/y);
	cout<<c;
    return 0;
}
19

Thanks, But why my code fails then, is __gcd(a,b) is different from Euclidean algo.

20

I checked… codes passes without euclidian algo too !!!
Can you please share your code ?

21

#include
#include
#include
#include
#include
using namespace std;

int main() {
long long int w,h,x,y;
cin>>w>>h>>x>>y;
if(y>h || x>w)
cout<<0;
else
cout<<(min((w/__gcd(x ,y)), (h/__gcd(x ,y))));
return 0;
}

22

You have divided by gcd(x,y) which is wrong…