(UVA) Electric Bill - Solution

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

First, based on the total amount to pay we need to discover the total amount of watts that was consumed. Then, we can apply a Binary Search to find out how many watts each person wasted.


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

class Main {
    public int totalAmount;
    public int diffAmounts;
    public int watts;
    public Info[] v;
   
    public int calcPrice(int w) {
        int consumption = 0;
        int amountToPay = 0;
        int index = 1;
        while (index < 4 && w > 0) {
            consumption = Math.min(w, (v[index].limit-v[index-1].limit));
            amountToPay += consumption*v[index].price;
            w -= consumption;
            index++;
        }
        amountToPay += w*7; // how much need to pay
       
        return amountToPay;
    }
   
    public int simulate(int myWatts) {
        // calculate how much I need to pay
        int myAmount = calcPrice(myWatts);
        // calculate how much my neighbor need to pay
        int neighborWatts = watts-myWatts;
        int neighborAmount = calcPrice(neighborWatts);

        if (neighborAmount-myAmount == diffAmounts) {
            return myAmount;
        } else if (neighborAmount-myAmount > diffAmounts) {
            return -1;
        }
        return -2;
    }
   
    public int binSearch(int lo, int hi) {
        if (lo > hi) {
            return -2;
        }
       
        int m = (lo+hi)/2;
        int myAmount = simulate(m);

        if (myAmount == -1) { // increase how much I need to pay
            return binSearch(m+1, hi);
        } else if (myAmount == -2) { // decrease how much I need to pay
            return binSearch(lo, m-1);
        } else {
            return myAmount;
        }
       
    }
   
    public void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        totalAmount = sc.nextInt();
        diffAmounts = sc.nextInt();
        v = new Info[5];
        v[0] = new Info(0, 0);
        v[1] = new Info(100, 2);
        v[2] = new Info(10000, 3);
        v[3] = new Info(1000000, 5);
        v[4] = new Info(0, 7);
        while (totalAmount != 0 || diffAmounts != 0) {
            int value = totalAmount;
            int index = 1;
            watts = 0; // total watts consumed (you+neighbor)
            while (index < 4 && value-((v[index].limit-v[index-1].limit)*v[index].price) >= 0) {
                value -= (v[index].limit-v[index-1].limit)*v[index].price;
                watts += v[index].limit-v[index-1].limit;
                index++;
            }
            if (value > 0) {
                value /= v[index].price;
                watts += value;
            }
           
            bw.write(binSearch(0, watts)+"\n");
            totalAmount = sc.nextInt();
            diffAmounts = sc.nextInt();
        }  
                                              
        bw.flush();
        bw.close();
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}

class Info {
    int limit;
    int price;
   
    public Info(int l, int p) {
        limit = l;
        price = p;
    }
}