K3002-Editorial

editorial
, ,
1

Problem Code: K3002

Problem Name: Empty Bucket

Problem link: Contest

Difficulty: Easy

Prerequisites:
Observation, math

Problem Statement:

Given two non negative integers a and b. You are required to answer whether it is possible to make a=0 and b=0 by applying the below operation any number of times:

  1. Subtract two from a and one from b.
  2. Subtract one from a and two from b.

Explanation:

Let a >= b, if not we swap the numbers.

Observation 1:
If a is greater than twice of b, the answer is NO.

Observation 2:

By combining both operations we can subtract three from both numbers. If a=b and a, b both are the multiple of 3, answer is YES.

Observation 3:

If after modulus of a and b by 3, one of them is 1 and other is 2, answer is YES. Otherwise, answer is NO.

Solution 
#include<bits/stdc++.h>
#define ll long long int
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
void main2()
{
     ll a,b;
     cin>>a>>b;
     if(a<b)
          swap(a,b);
     if(a>2*b)
          cout<<"NO\n";
     else
     {
          a%=3;
          b%=3;
          if(a<b)
              swap(a,b);
          if(a==0 && b==0)
              cout<<"YES\n";
          else if(a==2 && b==1)
              cout<<"YES\n";
          else
              cout<<"NO\n";
     }
     return;
}
int main()
{
   fast;
   ll t=1;
   cin>>t;
   while(t--)
   {
        main2();
   }
   return 0;
}

Feel free to share your approach, suggestions are welcome.

1 Like
2

Thank you sir for this explanation.

But please tell what is wrong in my approach -

                    a                b

x times 2 1
y times 1 2

let operation of subtracting 2 from a and 1 from b is done x number of times…
and let operation of subtracting 1 from a and 2 from b is done y number of times.

then a = 2x+y
b = x+2y
solving, we get x = (2a-b)/3, and y = x-a+b

if we get non negative integral solition of x, y, it is possible… else not.

3

hi,
your approach is correct but you have to check whether 2a-b is divisible by 3 or not.
If (2a-b) is not divisible by 3 then answer is “NO”.
for example:
a=0, b=2
answer is NO.