public class D { 
    
    /** = index of first occurrence of c in b[h..] 
      * Precondition: c is in b[h..] */
    public static int findFirst(int c, int[] b, int h) {
        // Store in i the index of the first c in b[h..] 
        
        int i= h;
        
        // inv: c is not in b[h..iÐ1] 
        while (b[i] != c) { 
            i= i + 1;
        }
        
        // R: b[i] == c and c is not in b[h..i-1] 
        return i;
    } 
    
    /** = a random int in 0..p.length-1; i is returned with probability p[i].
      * Precondition: the entries of p are positive and sum to at least 1. */
    public static int roll(double[] p) {
        double r= Math.random(); // r in [0,1) 
        
        // Think of the interval [0,1] as divided into segments of size p[i]. 
        // Store into i the segment number in which r falls. 
        int i= 0;  double pEnd= p[0]; 
        
        // inv: r >= sum of p[0] .. p[iÐ1]; iEnd = sum of p[0] .. p[i] 
        while ( r >= pEnd ) {
            pEnd= pEnd + p[i+1];
            i= i + 1;
        }
        // R: sum of p[0] .. p[iÐ1] <= r < sum of p[0] .. p[i] 
        
        return i; 
    }
    
    /** = an array r, where r[k] is the number of rolls out of
      * one million that resulted in the value k.  If roll() works
      * properly, then the numbers (counts) in r should be approximately
      * proportional to the numbers (probabilities) in p. */
    public static int[] testRoll(double[] p) {
        int[] r = new int[p.length];
        
        for (int i= 0; i < 1000000; i= i+1)
            r[roll(p)] += 1;
        
        return r;
    }
}