Allowance (POJ 3040)

This question asks you to find the ways to find a sum of coins that is larger or equal to (not exactly) a given value $V$. As to save money and compute the maximum of times to achieve this. We apply greedy strategies. That is, from the beginning, we always try to pay a lowest value with given coins that is larger or equal to $V$. We repeatly do this until the coins remains is not available for a valid payment.

To do this, we first pick coins from that of the largest value and move to coins of lower value and greedily spend them. If at last we get a sum that is exactly $V$ we stop here. If at last we get a sum less than $V$, we have to pick coins reversely from the smallest face value until we can cover the payment. By doing this we can get the lowest sum we can get from coins left that is valid.

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

class Coin implements Comparable<Coin>{
    int x;
    int y;
    public Coin(int x, int y) {
        this.x = x;
        this.y = y;
    }
    public int compareTo(Coin that) {
        Coin a = this;
        Coin b = that;
        return ((a.x == b.x) ? a.y - b.y : a.x - b.x);
    }
}

public class Allowance {
    private static boolean giveAllowance(Coin[] coins, int C) {
        for (int i = coins.length - 1; i >= 0; i--) {
            Coin c = coins[i];
            int spend = Math.min(c.y, C / c.x);
            c.y -= spend;
            C -= spend * c.x;
            if (C <= 0) return true;
        }
        for (int i = 0; i < coins.length; i++) {
            Coin c = coins[i];
            int spend = Math.min(c.y, C / c.x + ((C % c.x == 0) ? 0 : 1));
            c.y -= spend;
            C -= spend * c.x;
            if (C <= 0) return true;
        }
        return C <= 0;
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt(), C = in.nextInt();
        Coin[] coins = new Coin[N];
        for (int i = 0; i < N; i++) {
            coins[i] = new Coin(in.nextInt(), in.nextInt());
        }
        Arrays.sort(coins);
        int count = 0;
        while (giveAllowance(coins, C)) count++;
        System.out.println(count);
    }
}