Can someone please tell me what are the moves for the following
A=5 B=16?
use fast io in int main function and “\n” in place of endl rest everything is ok.
@pm_5289 First, you have to either add or subtract 1/16 then it would either become 1/4 or 3/8. Then if it becomes 1/4 and we add 1/4 to it it would become 1/2 (we can’t subtract as it would then become zero). then if once we got 1/2 we can take 1/2 and no matter what operation we do we would get either 0 or 1. Now moving on to the second case i.e, 3/8, we can give another 3/8, and then it would become 3/4 (as we can’t subtract as it would give us zero) then if we take 1/4 then it would become 1/2 (as if we would add 1/4 it would have become 1) then once it becomes 1/2 we can simply take the other number as 1/2 and then no matter what the operation would be it’s the guarantee that it would give either zero or 1.
why didn’t it worked with the concept of prime numbers.
Like all primes expect 2 will cause “No”.
Yes prime numbers other than 2 will give no but numbers which arent prime will also give no
Ex:-
9/10 7/40
public static void main (String[] args)
{
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
while (T-- > 0)
{
int a = sc.nextInt();
int b = sc.nextInt();
System.out.println((b&(b-1)) == 0 ? "Yes":"No");
}
}
what is wrong with my code, it is giving TLE…I couldn’t reduce after this…CC OP!
@surajkrmohanty use fast Input & output, I did the same mistake and hence wasn’t able to solve this problem during the contest but when i checked other’s people solution having correct verdict they all have used the fast input &output. you can also check my solution : CodeChef: Practical coding for everyone
How can X=15/16 can result in a win for Chef? Please explain. I only figured out that we can use Y=-1/16 for getting the chef to win, but ATQ Y must be positive. So can does 15/16 reduce to 0 or 1?
I haven’t checked this (nor read the Editorial ), but given X={a \over 2^k}, where a and 2^k are co-prime (and so a is odd) and a<2^k, Chef’s strategy is always to pick Y={1 \over 2^k}: then no matter if Divyam chooses to add or subtract Y, the result is either 0, 1, or {a' \over 2^{k-1}}, where a' is coprime to 2^{k-1}, a' < 2^{k-1} etc. Try it out with your example!
For fast io in python, use this -
Define iobio at start of your program once -
iobio = io.BytesIO(os.read(0, os.fstat(0).st_size))
Then, read each line of the input as follows -
line1 = iobio.readline().decode().strip()
line2 = iobio.readline().decode().strip()
line3 = iobio.readline().decode().strip()
int main() {
ll t,i,j,n,m,q,k,d,l,a,b,h,y,x,ans;
ios_base::sync_with_stdio(false);
cin.tie(0);
int c;
cin>>t;
while(t--)
{
cin>>a>>b;
ans=0;
a=b;
while(b>0)
{
ans++;
b/=2;
}
//ans=floor(log2(b));
ans--;
// cout<<(1<<ans)<<"\n";
if(a==(1<<ans))
cout<<"Yes\n";
else
cout<<"No\n";
}
Can you please tell me why it is giving wrong answer?
https://www.codechef.com/viewsolution/48253449
Thanks
int main() {
ll t,i,j,n,m,q,k,d,l,a,b,h,y,x,ans;
ios_base::sync_with_stdio(false);
cin.tie(0);
int c;
cin>>t;
while(t--)
{
cin>>a>>b;
ans=0;
a=b;
while(b>0)
{
ans++;
b/=2;
}
//ans=floor(log2(b));
ans--;
// cout<<(1<<ans)<<"\n";
if(a==(1<<ans))
cout<<"Yes\n";
else
cout<<"No\n";
}
Can you please tell me why it is giving wrong answer?
https://www.codechef.com/viewsolution/48253449
Thanks
Consider the test input:
1
1 8589934592
Yes it is giving No
but correct answer is Yes
Can you tell me the reason?
Is it due to (1<<ans) became out of range?
Thanks
Yes:
[simon@simon-laptop][13:39:58]
[~/devel/hackerrank/otherpeoples]>./compile-latest-cpp.sh
Compiling garvit2013-REALBIN.cpp
+ g++ -std=c++14 garvit2013-REALBIN.cpp -O3 -g3 -Wall -Wextra -Wconversion -DONLINE_JUDGE -D_GLIBCXX_DEBUG -fsanitize=undefined -ftrapv
garvit2013-REALBIN.cpp: In function ‘int main()’:
garvit2013-REALBIN.cpp:11:7: warning: unused variable ‘i’ [-Wunused-variable]
ll t,i,j,n,m,q,k,d,l,a,b,h,y,x,ans;
^
garvit2013-REALBIN.cpp:11:9: warning: unused variable ‘j’ [-Wunused-variable]
ll t,i,j,n,m,q,k,d,l,a,b,h,y,x,ans;
^
garvit2013-REALBIN.cpp:11:11: warning: unused variable ‘n’ [-Wunused-variable]
ll t,i,j,n,m,q,k,d,l,a,b,h,y,x,ans;
^
garvit2013-REALBIN.cpp:11:13: warning: unused variable ‘m’ [-Wunused-variable]
ll t,i,j,n,m,q,k,d,l,a,b,h,y,x,ans;
^
garvit2013-REALBIN.cpp:11:15: warning: unused variable ‘q’ [-Wunused-variable]
ll t,i,j,n,m,q,k,d,l,a,b,h,y,x,ans;
^
garvit2013-REALBIN.cpp:11:17: warning: unused variable ‘k’ [-Wunused-variable]
ll t,i,j,n,m,q,k,d,l,a,b,h,y,x,ans;
^
garvit2013-REALBIN.cpp:11:19: warning: unused variable ‘d’ [-Wunused-variable]
ll t,i,j,n,m,q,k,d,l,a,b,h,y,x,ans;
^
garvit2013-REALBIN.cpp:11:21: warning: unused variable ‘l’ [-Wunused-variable]
ll t,i,j,n,m,q,k,d,l,a,b,h,y,x,ans;
^
garvit2013-REALBIN.cpp:11:27: warning: unused variable ‘h’ [-Wunused-variable]
ll t,i,j,n,m,q,k,d,l,a,b,h,y,x,ans;
^
garvit2013-REALBIN.cpp:11:29: warning: unused variable ‘y’ [-Wunused-variable]
ll t,i,j,n,m,q,k,d,l,a,b,h,y,x,ans;
^
garvit2013-REALBIN.cpp:11:31: warning: unused variable ‘x’ [-Wunused-variable]
ll t,i,j,n,m,q,k,d,l,a,b,h,y,x,ans;
^
garvit2013-REALBIN.cpp:14:6: warning: unused variable ‘c’ [-Wunused-variable]
int c;
^
+ set +x
Successful
[simon@simon-laptop][13:40:03]
[~/devel/hackerrank/otherpeoples]>echo "1
1 8589934592" | ./a.out
garvit2013-REALBIN.cpp:31:15: runtime error: shift exponent 33 is too large for 32-bit type 'int'
No
Easy way if someone wants, (n & (n - 1)) gives us 0 if n^k is possible, or just do a bit count, if bit count is equal to 1 then print Yes else No because a single set bit is equal to power of 2
void solve(){
long long a,b;
cin>>a>>b;
if( (b &(b - 1)) == 0){
cout<<"Yes"<<endl;
}
else
cout<<"No"<<endl;
}
Please read the question properly. Chef can give any positive number but it’s Divyam’s choice to add or subtract.
Let me show how we’ll reach 0 or 1 from 15/16.
If X = 15/16 and chef gave 1/16, then upon addition it will become 1 and 7/8 if subtracted.
Once we reach 7/8, then chef will give 1/8. Add → 1, Subtract ->3/4
From 3/4 (chef can give 1/4), Add → 1, Subtract → 1/2
From 1/2 (chef can give 1/2), Add → 1, Subtract → 0.
This is how we are reaching 0 or 1 at the end. At every step, we have 2 choices i.e add or subtract, addition will lead convergence to 1 and subtraction to 0.
I hope you got the point. You may try for other cases like 15/32, 3/16 etc.
How the new numerator will be A mod p+A1 mod p in case 1 of editorial.Could u explain?
I am wondering if the testcase was A= 3 and B= 12 so in that casr our code will gives answer no for this and it should be YES for this because 3/12 = 1/4 that is 0.25 which is valid answer. Our code is only dividing denominator continuously by 2 and checking . How it would be considering this case where there is a common factor between numerator and denominator