It’s given that gcd(a, b) = 1 so A=3, B=12 is an invalid input.
didn’t understand the full proof for case 1,
but got the intuition that
a/b, gcd(a,b)=1
we cant vanish the prime factor from denominator other than 2
I am not able to get one thing that why they are taking X - Y = 0 and X + Y= 1.
Because chef will still win if X - Y is not equal to 0 and X + Y = 1.
If somebody knows what wrong with this then plz tell
2/5=0.4 now 0.4+0.6=1 so a=2, b=5 as input shouldn’t give ans as yes?
can’t this be also true, if initially we have X = 1/3 and we have to make X = 1/2 so we take Y=1/6 and we get X = 1/3+1/6 =3/6=1/2 and then X will be a multiple of 1/2 hence we will get our answer
can someone tell me what is wrong with my code?
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t,i,a,b;
cin>>t;
for(i=0;i<t;i++)
{
cin>>a>>b;
while(b%2==0)
b=b/2;
if(b==1)
cout<<"Yes"<<'\n';
else
cout<<"No"<<'\n';
}
return 0;
}
Are you certain that with the choice of 1/6 Chef is guaranteed to win? What about the case when rather than adding, Divyam subtracts 1/6 from 1/3 as it is his call not Chef’s whether the number chosen is added or subtracted. The question asks whether there is a strategy where Chef is guaranteed to win, which means he shall win irrespective of Divyam’s decision. In the example you are insisting upon, if Divyam subtracts the chosen number Chef will be left with 1/6 rather than 1/5. Divyam can prevent Chef from reaching 1 or 0 in all cases except the ones with the denominator a power of 2.
umm okay but how do i resolve it? I tried to declare b in long long int too still it gives me wrong answer
The question asks whether or not there is a strategy that guarantees that Chef will win in a finite number of turns. This means winning irrespective of Divyam’s decision to add or subtract the chosen number. In the case of 0.4, if Chef chooses 0.6 and Divyam chooses to subtract rather than add, then Chef shall be left with another non binary number. This means that the choices you mentioned do not guarantee that Chef will win, thus the answer should be no.
Link to your updated solution?
ahh, never mind I forgot to declare a as long long int, silly mistake! Thanks BTW!
yes, I got that wrong, thankyou for clarification, the test cases were weak my wrong answer passed during the contest.
Well a much better way would be to use Bit Manipulation to check whether its power of 2 or not
(b&(b-1)) == 0 then its a power of two
if (b&(b-1)) cout << “NO\n”;
else cout << “YES\n”;