(UVA) Exact Sum - Solution

I used Binary Search to solve this problem.


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

class Main  {
    public static int[] booksPrices;
   
    public static int binarySearch(int lo, int hi, int money) {
        if (lo > hi) {
            return -1;
        }
       
        int mi = (lo+hi)/2;
        if (booksPrices[mi] > money) {
            return binarySearch(lo, mi-1, money);
        }
        else if (booksPrices[mi] < money) {
            return binarySearch(mi+1, hi, money);
        }
        else {
            return money;
        }
    }
   
    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 static void process() throws NumberFormatException, IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
       
        String line = br.readLine();
        while (line != null) {
            int numAvailableBooks = Integer.parseInt(line);
            booksPrices = new int[numAvailableBooks];
            for (int i = 0; i < numAvailableBooks; i++) {
                booksPrices[i] = reader(br);
            }
            int money = reader(br);
           
            Arrays.sort(booksPrices);
           
            int bestPriceBook1 = 0;
            int bestPriceBook2 = 1000000000;
            for (int i = 0; i < numAvailableBooks; i++) {
                int priceBook1 = booksPrices[i];
                int priceBook2 = binarySearch(i+1, numAvailableBooks-1, money-priceBook1);
                if (priceBook2 > -1) {
                    if (Math.abs(priceBook2-priceBook1) < Math.abs(bestPriceBook2-bestPriceBook1)) {
                        bestPriceBook1 = priceBook1;
                        bestPriceBook2 = priceBook2;
                    }
                }
            }
           
            bw.write("Peter should buy books whose prices are " + bestPriceBook1 + " and " + bestPriceBook2 + ".\n\n");
           
            line = br.readLine();
            if (line.equals("")) {
                line = br.readLine();
            }
        }
       
        bw.flush();
        bw.close();
                                               
        return;
    }
  
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        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