(UVA) Closest Sums - Solution 1

Brute Force was used to solve this problem.


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

class Main {
    public static int reader(BufferedReader br) throws NumberFormatException, IOException {    
        int n;
        int resp = 0;    
        int signal = 1;
      
        while (true) {        
            n = br.read();        
            if (n >= '0' && n <= '9') {
                break;
            }
            if (n == '-') {
                signal = -1;
            }
            if (n == '+') {
                signal = 1;
            }
        }
          
        while (true) {        
            resp = resp*10 + n-'0';        
            n = br.read();        
            if (n < '0' || n > '9') {
                break;    
            }
        }
     
        return resp*signal;    
    }
  
    public static void process() throws NumberFormatException, IOException { 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      
        int numCase = 0;
        int qtyNum = reader(br);
        while (qtyNum > 0) {
            int[] setInt = new int[qtyNum];
            for (int i = 0; i < qtyNum; i++) {
                setInt[i] = reader(br);
            }
          
            int qtyQueries = reader(br);
            int[] queries = new int[qtyQueries];
            for (int i = 0; i < qtyQueries; i++) {
                queries[i] = reader(br);
            }
          
            ArrayList<Integer> sums = new ArrayList<Integer>();
            for (int i = 0; i < qtyNum; i++) {
                for (int j = i+1; j < qtyNum; j++) {
                    int sum = setInt[i]+setInt[j];
                    sums.add(sum);
                }
            }
          
            Collections.sort(sums);
          
            System.out.println("Case " + ++numCase + ":");
            for (int i = 0; i < qtyQueries; i++) {
                int index = 0;
                int shortDiff = 2000000000;
                for (int j = 0; j < sums.size(); j++) {
                    int diffPrevious = Math.abs(queries[i]-sums.get(j));
                    if (diffPrevious < shortDiff) {
                        shortDiff = diffPrevious;
                        index = j;
                    }
                }
              
                System.out.println("Closest sum to " + queries[i] + " is " + sums.get(index) + ".");
            }
          
            qtyNum = reader(br);
        }
                  
        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