(SPOJ) Pão a metro - Solution

Link to the problem: http://br.spoj.com/problems/PAO07/

The solution below used Binary Search to find the biggest length of bread that it is enough for everybody.


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

class solucao {
    public int[] sandwiches;
    public int numSandwiches;
    public int numPeople;
   
    public int cutBread(int length) {
        int numBread = 0;
        for (int i = 0; i < numSandwiches; i++) {
            int leftover = sandwiches[i];
            while (leftover >= length) {
                leftover -= length;
                numBread++;
            }
        }

        if (numBread >= numPeople) {
            return 1;
        }
        else { // if (numBread < numPeople)
            return -1;
        }
    }
   
    // return the biggest length of bread that it is enough for everybody
    public int binSearch(int lo, int hi, int best) {
        if (lo > hi) {
            return best;
        }
       
        int m = (lo+hi)/2;
        int result = cutBread(m);

        if (result == 1) {
            return binSearch(m+1, hi, m);
        }
        else { // if (result == -1)
            return binSearch(lo, m-1, best);
        }
    }
   
    public static int reader(BufferedReader br) throws NumberFormatException, IOException {     
        int n;
        int resp = 0;     
      
        while (true) {         
            n = br.read();         
            if (n >= '0' && n <= '9') {
                break;
            }
        }
           
        while (true) {         
            resp = resp*10 + n-'0';         
            n = br.read();         
            if (n < '0' || n > '9') {
                break;     
            }
        }
      
        return resp;     
    }
   
    public void process() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
       
        numPeople = reader(br);
        numSandwiches = reader(br);
       
        sandwiches = new int[numSandwiches];
        int maxLengthBread = 0;
        for (int i = 0; i < numSandwiches; i++) {
            sandwiches[i] = reader(br);
            maxLengthBread = Math.max(maxLengthBread, sandwiches[i]);
        }
       
        int length = binSearch(1, maxLengthBread, 0);
       
        bw.write(length+"\n");
           
        bw.flush();
        bw.close();
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        solucao m = new solucao();
        m.process();
       
        System.exit(0);
    }
}

Comments

Popular posts from this blog

(Coderbyte) Powers of Two - Solução

(Coderbyte) Dash Insert II - Solução

(CoderByte) Number Search - Solução