[UVa] 12032 - The Monkey and the Oiled Bamboo

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\n",kase++,k);
 
 }
 return 0;
}