pranay_teja
10/22/2018 - 9:32 AM

GFG-Camel_Bananas

#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;
}