Algorithm
problem link- https://www.spoj.com/problems/POUR1/
POUR1 - Pouring water
Given two vessels, one of which can accommodate a litres of water and the other - b litres of water, determine the number of steps required to obtain exactly c litres 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
An integer t, 1<=t<=100, denoting the number of testcases, followed by t sets of input data, each consisting of three positive integers a, b, c, not larger than 40000, given in separate lines.
Output
For each set of input data, output the minimum number of steps required to obtain c litres, or -1 if this is impossible.
Example
2 5 2 3 2 3 4Sample output:
2 -1
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <map>
#include <list>
using namespace std;
int gcd(int a,int b){
if(b==0)return a;
return gcd(b,a%b);
}
int main(){
int t;
scanf("%d",&t);
while(t--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(c>max(a,b)||c%gcd(a,b)!=0){
printf("-1\n");
continue;
}
int acount=0,bcount=0;
int tempa=0,tempb=0;
while(true){
//cout<<tempa<<" "<<tempb<<endl;
if(tempa==c||tempb==c)break;
if(tempa==0){
tempa=a;
acount++;
continue;
}
if(tempb!=b){
int val=min(tempa,b-tempb);
tempb+=val;
tempa-=val;
acount++;
continue;
}
if(tempb==b){
tempb=0;
acount++;
continue;
}
}
tempa=0;tempb=0;
while(true){
//cout<<tempa<<" "<<tempb<<endl;
if(tempa==c||tempb==c)break;
if(tempb==0){
tempb=b;
bcount++;
continue;
}
if(tempa!=a){
int val=min(tempb,a-tempa);
tempa+=val;
tempb-=val;
bcount++;
continue;
}
if(tempa==a){
tempa=0;
bcount++;
continue;
}
}
printf("%d\n",min(acount,bcount));
}
return 0;
}Input
5
2
3
2
3
4
Output
-1
Demonstration
SPOJ Solution-Pouring water-Solution in C, C++, Java, Python