Skip to content

UVA Problem: 12032 (The Monkey and the Oiled Bamboo)

October 5, 2011

Problem Statement:

Problem Explanation:

This problem may seems complicated at the the first glance, But if closely observed then it becomes apparent that there is only a few candidate for minimum value of k. First find what can be the maximum of (minimum value of k). If the maximum difference between any two rung of ladder is n, then maximum of (minimum value of k) is n+1, since in this case no decrement is performed for k, and certainly all rung can be reached, since n is the highest difference. Next comes the question can we minimize k from (n+1). Since maximum difference between any two rung is n, so k must at least n. So now check whether it is possible to reach all rung using value n, if possible then print n, else print n+1. Simple is in’t?

Advertisements
No comments yet

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: