pranay_teja

10/22/2018 - 9:32 AM

```
#include <bits/stdc++.h>
using namespace std;
/*
A person has 3000 bananas and a camel. The person wants to transport maximum number of bananas to a destination which is 1000 KMs away,
using only the camel as a mode of transportation. The camel cannot carry more than 1000 bananas at a time and eats a banana every km it travels.
What is the maximum number of bananas that can be transferred to the destination using only camel (no other mode of transportation is allowed).
*/
// #GFG
// http://www.geeksforgeeks.org/puzzle-15-camel-and-banana-puzzle/
void ctn(vector<int> &a,int i,int max,int fuel){
//it is ensured that bananas>=fuel from the first while loop
int load;
if(a[i]>=max){
load=max; //load max the camel can carry
a[i]-=load;//remaining bananas at the location
a[i+1]+=(load-fuel);//deliver the load to next location
}else{
load=a[i]; //load all the bananas
a[i]-=load; // as all bananas are loaded
a[i+1]+=(load-fuel);
}
}
void gbtc(vector<int> &a,int j,int max,int fuel){
//it is ensured that bananas>fuel from second while loop(to gain any bananas by coming back)
//here j=i+1
a[j]-=fuel;//need fuel to go back_inserter
ctn(a,j-1,max,fuel);
}
int main(){
int ban;//total bananas
int dis;//total distance
int max;//max bananas camel can carry
int fuel;//bananas camel eats for each km
cout<<endl<<"bananas"<<endl;
cin>>ban;
cout<<endl<<"distance"<<endl;
cin>>dis;
cout<<endl<<"max capacity of camel"<<endl;
cin>>max;
cout<<endl<<"camel fuel"<<endl;
cin>>fuel;
vector<int> a(dis+1);
int i=0;
a[0]=ban; //starting point
while(i<dis){ //runs upto last but 1 location(dis-1)| dis is the last location
//eg 1000 distance->1001 size of array->last element index 1000->runs upto 999
if(a[i]>=fuel){
ctn(a,i,max,fuel); //(carry to next)if camel can reach to the next location with the current bananas
// move to the next location
while(a[i]>fuel){
gbtc(a,i+1,max,fuel); //if we can gain any bananas by going back
//(go back to carry) them to present location
}
}
i++;
}
cout<<a[dis]<<endl;
return 0;
}
```