Problem Name :  The Monkey and the Oiled Bamboo

Problem Link : See Problem :  Uva 12032

Let, the height of the rungs from the ground are 2, 8, 11, 16, 21 respectively
maximum distance is 6, k=6
Jumped 2 foot from the ground to the 1st rung (ground to 1). Since I jumped less than k feet, k remains 6. 

Jumped 6 feet for the next rung (2 to 8). Since I jumped equal k feet, k becomes 5. 
Jumped 3 foot for the 3rd rung (8 to 11). So, k remains 5. 
Jumped 5 feet for the 4th rung (11 to 16). This k becomes 4. 
Jumped 5 feet for the 5th rung (16 to 21). This time i need to jump 5 but k is 4, you can’t complete the process.
So, the Ans = 6+1=7

Solution  :

#include<bits/stdc++.h>
#define pb push_back
#define read freopen("input.txt","r",stdin)
#define write freopen("output.txt","w",stdout)
#define rev(s) std::reverse(s.begin(), s.end())
//#define up std::transform(s.begin(), s.end(), s.begin(), ::toupper);
///string sb=s.substr(1,3);

#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*b)/gcd(a,b)

#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define min4(a,b,c,d) min(min(a,b),min(c,d))
#define max4(a,b,c,d) max(max(a,b),max(c,d))

#define INF (1<<28)
#define mod 1000000007

#define PI acos(-1.0)

#define tbeg clock_t _t=clock();
#define tend cout << "\n\nTime: " << (double)(clock()-_t)/CLOCKS_PER_SEC;

//#define PI 2*acos(0.0)
//#define 2ndPI acos(-1.0)
#define lowest std::transform(s.begin(), s.end(), s.begin(), ::tolower);
#define n2s(n) stringstream ss; ss<<n; string Get=ss.str()
#define CC(x) cout<<(x)<<endl
#define srt sort(a,a+n)
#define rep(i,n) for(long long i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define pi 2*acos(0)

typedef long long LL;

using namespace std;

LL BigMod(LL B,LL P,LL M){ LL R=1; while(P>0)  {if(P&1){R=(R*B)%M;}P/=2;B=(B*B)%M;} return (LL)R;} //compute b^p%m

int main()
{
    //read;
    //write;
    LL t, n, x, a, N, tc = 0;
    scanf("%lld",&t);
    while(t--)
    {
        LL Ans = 0;
        scanf("%lld",&n);
        scanf("%lld",&a);
        Ans = a;
        LL A[100009], T = 1;
        A[T++] = a;
        A[0] = 0;
        n = n - 1;
        while(n--)
        {
            scanf("%lld",&N);
            A[T++] = N;
            LL ans = N - a;
            Ans = max(Ans,ans);
            a = N;
        }
        LL k = Ans, ANS = 0;
        rep(i,T-1)
        {
            if((A[i+1] - A[i])==k) k--;
            else if((A[i+1] - A[i])>k){Ans = Ans + 1; break;}
        }
        printf("Case %lld: %lld\n",++tc,Ans);
    }
    return 0;

}
Advertisements