(UVA) The Monkey and the Oiled Bamboo - Solution

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3183

We start this problem with the information of the maximum value of k. Then, we can use Binary Search to discover the minimum value of k. For every possible value, we need to simulate if the monkey can reach the top rung.


import java.io.*;
import java.util.*;

class Main {
    public int best;
    public int[] distances;
    public int numRungs;
   
    public boolean simulate(int strength) {
        int previous = 0;
        for (int i = 0; i < numRungs; i++) {
            int distance = distances[i]-previous;
            if (distance > strength) {
                return false;
            }
            if (distance == strength) {
                strength--;
            }
            previous = distances[i];
        }
        return true;
    }
   
    public int binSearch(int lo, int hi, int best) {
        if (lo > hi) {
            return best;
        }
       
        int m = (lo+hi)/2;
        boolean isPossible = simulate(m);
        if (isPossible) {
            return binSearch(lo, m-1, m);
        }
        else {
            return binSearch(m+1, hi, best);
        }
    }
   
    public void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
       
        int numTests = sc.nextInt();
        for (int test = 0; test < numTests; test++) {
            numRungs = sc.nextInt();
            distances = new int[numRungs];
            int previous = 0;
            for (int i = 0; i < numRungs; i++) {
                distances[i] = sc.nextInt();
            }       
            int min = binSearch(distances[0], distances[numRungs-1], -1);
           
            bw.write("Case "+(test+1)+": "+min+"\n");
        }
                                              
        bw.flush();
        bw.close();
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}