if((a+b)%3==0)
how is this true
I solved it using binary search, but it seems like it had a way simpler solution.
void solve() {
ll n, temp, a, b, ans = 0;
cin >> a >> b;
if(a == 2 * b || b == 2 * a) {
cout << "YES" << endl;
return;
}
if(a == 0 || b == 0) {
cout << "NO" << endl;
return;
}
ll start = 0, end = max(a, b);
while(start < end) {
ll mid = (start + end)/2;
if(a - mid == 2 * (b - 2 * mid) && a - mid > 0) {
cout << "YES" << endl;
return;
}
if(a - mid > 2 * (b - 2 * mid)) end = mid;
else start = mid + 1;
}
cout << "NO" << endl;
}
@prashant2020
let’s think about extreme condition , everytime you take 2 coin from a and 1 from b .
then also, a ratio b will be exact 2;
or else, their ratio will be less than 2; hence, it can never succeed 2;
Hope it helps.
Can you please explain why are you checking for (2a >= b && 2b >=a).
Thank you.
But with this alone we cant completely say for sure that our answer will be true. For instance take 11,4
11+4 = 15
But in this Case Our answer is false
For a certain answer we have to consider another condition which is that is (max(a, b) > 2 * min(a, b)
don’t worry about it just consider two condition and you will be just fine
- ( a + b ) % 3 == 0
- max(a, b) > 2 * min(a, b)
but with condition you don’t have to swap piles.
and for your Question just imagine 11 and 4 even if you take 2 from 11 you wont be able to reach zero before stack b is completely empty
you will only be able to take down 8 coins before stake b is empty.
Just imagine 11 and 4 even if you take 2 from 11 you wont be able to reach zero before stack b is completely empty
you will only be able to take down 8 coins before stake b is empty.
Its Just to remove this kind of cases where ( a + b )%3==0
or you can just do
max(a, b) > 2 * min(a, b)
its same thing but you don’t have to check for both stacks individually or swap the stacks.
What I did was I assumed A > B (using swap).
Let the difference between A and B be “Diff”. We know that through our sequence of moves, the net total we remove from A is “diff” more than B. If we look at Move 1 and 2, when we do move 1, the difference between A and B becomes 1 smaller (and vice versa). So, in order to finish at the same time, we need to get rid of the difference. Let’s do that first. We find the difference “Diff”, and then subtract 2 * Diff from A and just Diff from B (this is the number of coins we took away through Move 1, which is 2 coins from A and 1 coin from B). Now, if B is negative, that means that we cannot get rid of the difference between A and B in time, so print “NO”. If it is positive, then now we have A and B equal (after removing the difference). From Move 1 and 2, the only way we can remove an equal amount is with 2 moves: first is Move 1, and second is Move 2 (so through 2 moves, we remove 3 each). This is the only way, so now we simply check if B is divisible by 3, and then return “YES” or “NO” according to the result (note that we could have checked if A was >0 and divisible by 3 as well, I just used B for convenience).
The logic behind the question:
- In every operation we are decreasing 2 from left and 1 from right or 1 from left and 2 from right, that is total decreased by 3, so if we want both equal to zero at the end of operation then a summation of both numbers must be divisible by 3.
- max of the both numbers must be less than or equal to min of both numbers. (try to think about a=11, b=4).
Code:
ll a,b;
cin>>a>>b;
if(a==0 && b==0)
{
cout<<"YES\n";
continue;
}
else if(a==0 || b==0) cout<<"NO\n";
else if((a+b)%3==0 && (max(a,b))/2<=min(a,b)) cout<<"YES\n";
else cout<<"NO\n";#include <bits/stdc++.h>
using namespace std;
int main(){
long t;
cin >>t;
long long a,b;
while (t--)
{
cin >> a>>b;
if(((a+b)%3==0 )&& (abs(a-b)<=min(a,b))){
cout << "YES"<<endl;
}else{
cout << "NO"<<endl;
}
}
return 0;
}