Monkey

It's time to remember the disastrous moment of the old school math. Yes, the little math problem with the monkey climbing on an oiled bamboo. It goes like this:

"A monkey is trying to reach the top of an oiled bamboo. When he climbs up 3 feet, he slips down 2 feet. Climbing up 3 feet takes 3 seconds. Slipping down 2 feet takes 1 second. If the pole is 12 feet tall, how much time does the monkey need to reach the top?"

When I was given the problem, I took it seriously. But after a while I was thinking of killing the monkey instead of doing the horrible math! I had rather different plans (!) for the man who oiled the bamboo.

Now we, the problem-setters, got a similar oiled bamboo. So, we thought we could do better than the traditional monkey. So, I tried first. I jumped and climbed up 3.5 feet (better than the monkey! Huh!) But in the very next second I just slipped and fell off to the ground. I couldn't remember anything after that, when I woke up, I found myself in a bed and the anxious faces of the problem setters around me. So, like old school times, the monkey won with the oiled bamboo.

So, I made another plan (somehow I want to beat the monkey), I took a ladder instead of the bamboo. Initially I am on the ground. In each jump I can jump from the current rung (or the ground) to the next rung only (can't skip rungs). Initially I set my strength factor k. The meaning of k is, in any jump I can't jump more than k feet. And if I jump exactly k feet in a jump, k is decremented by 1. But if I jump less than k feet, k remains same.

For example, let the height of the rungs from the ground be 1, 6, 7, 11, 13 respectively and k be 5. Now the steps are:

Jumped 1 foot from the ground to the 1^st rung (ground to 1). Since I jumped less than k feet, k remains 5.
Jumped 5 feet for the next rung (1 to 6). So, k becomes 4.
Jumped 1 foot for the 3^rd rung (6 to 7). So, k remains 4.
Jumped 4 feet for the 4^th rung (7 to 11). Thus k becomes 3.
Jumped 2 feet for the 5^th rung (11 to 13). And so, k remains 3.

Now you are given the heights of the rungs of the ladder from the ground, you have to find the minimum strength factor k, such that I can reach the top rung.

Input

Input starts with an integer T (≤ 10), denoting the number of test cases.

Each case starts with a line containing an integer n (1 ≤ n ≤ 10⁵) denoting the number of rungs in the ladder. The next line contains n space separated integers, r₁, r₂ ..., r_n (1 ≤ r₁ < r₂ < ... < r_n ≤ 10⁹) denoting the heights of the rungs from the ground.

Output

For each case, print the case number and the minimum possible value of k as described above.

Sample

Sample Input	Sample Output
Click to copy 2 5 1 6 7 11 13 4 3 9 10 14	Click to copy Case 1: 5 Case 2: 6

Notes

Dataset is huge, use faster I/O methods.

LOJ 1425- The Monkey and the Oiled Bamboo

Suppose you have a bamboo and you have to climb up using it.But here you can't skip any step when you climb up. You must climb up step by step. Here you are also given an energy k.It means you climb up at most k steps. When you jump and goto k steps then k will be decrease by one. So we can easily find that we can at most k-1 height jump. Again if you jump k-1 heights, then you can jump at most k-2 heights. Here you are given the height of every steps of the bamboo. Now you have to find k that which you cross all the steps using this k. You have to find k as minimum as possible.

Solution approach:

We can use difference array to solve this problem. At first we calculate all the difference between two neighbouring index. Then sort the difference array and store the maximum difference into a variable.Ex: int a=diff[lastPostion-1] -1; After all iterate the whole array and check by this value if it equal to the next difference then decrease the value of a, otherwise break the loop. If the value of each of the difference arrays is difference 1, then in the end the last value of the difference array is the answer, otherwise we can get the answer by adding 1 to the last value.

If you are still stuck with this problem, check the codes below:

C++

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m;
    cin>>n;
    for(int i1=0;i1<n;i1++)
    {
        int a[100000]= {0},tt=0,i,j,c=0,x,k,l,p=1,b[100000]= {0};
        cin>>m;
        for(i=0;i<m;i++)
            cin>>a[i];
        b[0]=a[0];
        for(i=1; i<m; i++)
        {
            b[p++]=a[i]-a[i-1];
        }
        sort(b,b+p);
        x=b[p-1]-1;
        for(i=p-2; i>=0; i--)
        {
            if(x==b[i])
                x--;
            else if(x<b[i])
            {
                tt=1;
                break;
            }
        }
        if(tt==1)
        {
            printf("Case %ld: %ld\n",i1+1,b[p-1]+1);
        }
        else
            printf("Case %ld: %ld\n",i1+1,b[p-1]);

    }
    return 0;
}

Tutorial source

Input

Output

Sample

Notes

Total Submissions

Users Tried

Users Solved

LOJ 1425- The Monkey and the Oiled Bamboo

C++