runtah

A very simple problem but the conditions have to be understood very carefully.

Method: Simple, on the fly.

Initialize the value of k with the first jump (from ground to first rung)
If (jump == capacity)
 capacity decreases by 1
If (jump > current capacity)
 Check if jump == k, increase k by 1. Reset capacity to k
 Check if jump > k, set k = jump, Reset capacity to k-1
 Check if jump < k increase k by 1. Reset capacity to k

#include <stdio.h>

typedef int lint;



lint val[100000 + 10];

int main( void ) {
 
 lint n, i, k, v, kase=1, kounter;
 
 val[0]=0;
 
 scanf("%d",&kounter);
 
 while (kounter--) {
 scanf("%d",&n);
 
 for (i=1 ; i<=n ; i++) {
 scanf("%d",&val[i]);
 }
 
 k = val[1];
 v = val[1];
 
 for (i=0 ; i<n ; i++) {
 if (val[i+1]-val[i]>v) {
 if (val[i+1]-val[i]==k) {
 k++;
 v=k;
 } else if (val[i+1]-val[i]>k) {
 k=val[i+1]-val[i];
 v=k-1;
 } else {
 k++;
 v=k;
 }
 } else if (val[i+1]-val[i]==v) {
 v--;
 }
 
 }
 printf("Case %d: %d ",kase++,k);
 
 }
 return 0;
}