Pouring Water | CodeChef Solution

Hello coders, today we are going to solve Pouring Water CodeChef Solution whose Problem Code is POUR1.

Task

Given two vessels, one of which can accommodate a liters of water and the other which can accommodate b liters of water, determine the number of steps required to obtain exactly c liters of water in one of the vessels.

At the beginning both vessels are empty. The following operations are counted as ‘steps’:

• emptying a vessel,
• filling a vessel,
• pouring water from one vessel to the other, without spilling, until one of the vessels is either full or empty.

Input Format

An integer t, 1<=t<=100, denoting the number of test cases, followed by t sets of input data, each consisting of three positive integers a (the number of liters the first container can hold), b (the number of liters the second container can hold), and c (the final amount of liters of water one vessel should contain), not larger than 40000, given in separate lines.

Output Format

For each set of input data, output the minimum number of steps required to obtain c liters, or -1 if this is impossible.

Example

Sample Input

2
5
2
3
2
3
4

Sample Output

2
-1

Solution – Pouring Water

C++

#include <bits/stdc++.h>
#define GREEN "\033[32m"
#define MAGENTA "\033[35m"
#define RESET "\033[0m"
#define all(x) begin(x),end(x)
#define sz(x) (int)(x).size()
using namespace std;
#ifdef BCDBG
#define tcT template<typename T
tcT,typename U> ostream& operator<<(ostream& os,const pair<T,U>& p) {return os<<"("<<p.first<<", "<<p.second<<")";}
tcT,typename U=typename enable_if<!is_same<T,string>::value,typename T::value_type>::type> ostream& operator<<(ostream &os,const T &v)
{os<<"\n{";string sep;for(const U &x:v)os<<sep<<x,sep=", ";return os<<'}';}
void debug_help() {cout<<RESET<<endl;}
tcT,typename... U> void debug_help(T t,U... u) {cout<<t;if(sizeof...(u))cout<<", ";debug_help(u...);}
int debug_dms[10],debug_md;
void debug_fill() {}
tcT,typename... U> void debug_fill(T t,U... u) {debug_dms[debug_md++]=t;debug_fill(u...);}
tcT> void debug_arr(T x,int d) {cout<<x;}
tcT> void debug_arr(T* arr,int d)
{cout<<"\n{";string sep;for(int i=0;i<debug_dms[d];i++)cout<<sep,sep=", ",debug_arr(arr[i],d+1);cout<<'}';if(d==0)cout<<RESET<<endl;}
#define dbg(...) cout<<MAGENTA<<__LINE__<<" ["<<#__VA_ARGS__<<"]: "<<GREEN,debug_help(__VA_ARGS__)
#define dba(arr,...) cout<<MAGENTA<<__LINE__<<" ["<<#arr<<"]: "<<GREEN,debug_md=0,debug_fill(__VA_ARGS__),debug_arr(arr,0)
#else
#define dbg(...)
#define dba(arr,...)
#endif
typedef long long ll;
typedef unsigned long long ull;
const char df = '\n';

int go(int A, int B, int c) {
  int ct = 1, a = A, b = 0;
  while (a != c && b != c) {
    if (a == 0) {
      a = A;
      ct++;
    } else if (b == B) {
      b = 0;
      ct++;
    } else {
      int m = min(B - b, a);
      a -= m;
      b += m;
      ct++;
    }
  }
  return ct;
}

void solve() {
  int a, b, c;
  cin >> a >> b >> c;
  if (c % __gcd(a, b) || (c > a && c > b)) {
    cout << -1 << df;
    return;
  }
  cout << min(go(a, b, c), go(b, a, c)) << df;
}

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tt = 1;
  cin >> tt;
  for (int i = 1; i <= tt; i++) {
    solve();
  }
  return 0;
}

Python

import math
def pour(a,b,c):
    step=0
    ves1=a
    ves2=0
    step+=1
    while(ves1!=c and ves2!=c):
        if(ves2==b):
            ves2=0
            step+=1
        elif(ves1==0):
            ves1=a
            step+=1
        else:
            capcty=b-ves2
            donow=min(ves1,capcty)
            ves2+=donow
            ves1-=donow
            step+=1
    return step      
            
for i in range(int(input())):
    a=int(input())
    b=int(input())
    c=int(input())
    if(c>a and c>b)or c%math.gcd(a,b)!=0:
        print("-1")
    else:
        
        au1 = pour(a, b, c)
        ao2 = pour(b, a, c)
        print(min(au1, ao2))

Java

import java.io.*;
import java.util.*;
import java.lang.*;

public class Main
{
    public static void main(String args[])
    {
       Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        for(int i=0;i<t;i++)
        {
            int a=sc.nextInt();
            int b=sc.nextInt();
            int c=sc.nextInt();
            if(a>=c || b>=c)
            {
                if(c%gcd(a,b)==0)
                {
                    
                    System.out.println(Math.min(count(a,b,c),count(b,a,c)));
                }
                else
                {
                    System.out.println(-1);
                }
            }
            else
            {
                System.out.println(-1);
            }
        }
    }
    
    static int gcd(int a,int b)
    {
        if(b==0)
        {
            return a;
        }
        else
        {
            return gcd(b,a%b);
        }
    }
    static int count(int a,int b,int c)
    {int c1=0;
     int c2=0;
     int count=0;
        while(c1!=c && c2!=c)
       {
           if(c1==0)
            {
                c1=a;
                count++;
            }
            else if(c2==b)
            {
                c2=0;
                count++;
            }
            else
            {
                int x=c1;
                
                c1=c1-(b-c2);
                c2=c2+x;
                if(c2>b)
                {
                    c2=b;
                    count++;
                }
                 if(c1<0)
                {
                    c1=0;
                    count++;
                }
                
            }
           
       }
        
        return count;
        
            
   }
}

Disclaimer: The above Problem (Pouring Water) is generated by CodeChef but the Solution is Provided by CodingBroz. This tutorial is only for Educational and Learning Purpose.