UVA 12032 The Monkey and the Oiled Bamboo

i

2
5
1 6 7 11 13
4
3 9 10 14

p12032.cpp

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100010
int rungs[MAXN];

bool simul(int n, long long int k){
	// if (k < rungs[0]) return false;
	// if (k == rungs[0]) k--;
	for(int i = 1; i <= n; ++i){
		int diff = rungs[i] - rungs[i - 1];
		if (k == diff) k--;
		else if (k < diff) return false;
	}
	return true;
}

int main(){
	ios_base::sync_with_stdio(false);		//has no effect
	rungs[0] = 0;	//sentinel
	int tc, n, cnt = 0;
	long long int sum;
	// cin >> tc;
	scanf("%d", &tc);
	while (tc--){
		// cin >> n;
		scanf("%d", &n);
		cnt++;
		sum = 0;
		for (int i = 1; i <= n; ++i){
			// cin >> rungs[i];
			scanf("%d", &rungs[i]);
			sum += rungs[i];
		}

		//binary search the answer
		long long int lo = 1, hi = sum + 1;
		long long int mid, best;
		while (lo <= hi){
			mid = lo + (hi - lo) / 2;
			if (simul(n, mid))
				best = mid, hi = mid - 1;
			else lo = mid + 1;
		}
		// cout << "Case " << cnt << ": " << best << endl;
		printf("Case %d: %lld\n", cnt, best);

	}
}

/*
Time without i/o optimisation 0.140
Time with i/0 optimiations 0.05
*/