October 2005 Problem 'allow' Analysis

The sake of explanation, suppose the coins are 1c, 5c, 10c, 50c and 100c. There are some observations that can be made (and obviously generalised to other sets of coins):

1. The order in which payments are made is arbitrary, so we can construct them in increasing order of amount. We also assume that each payment is minimal, in the sense that no coin could be removed from the payment without causing underpayment. We can in fact make a slightly stronger assumption: it is impossible to take left-over coins at the end, add them to some payment and then remove coins from that payment to reduce its amount without underpaying.
2. Any payment should be the salary rounded up to a multiple of one of the coin sizes. In any other payment, there is guaranteed to be a coin small enough to be removed without causing underpayment. By the previous observation, the payments are first exact, then rounded up to a multiple of 5c, then to a multiple of 10c and so on.
3. In most cases, rounding up before it is necessary is not a good idea e.g. switching from 33c to 35c requires more 5c pieces, by minimality the 1c coins can never be used again. Similarly, switching from 38c to 40c early is bad: the 5c pieces can never be used again, because we still have 3 1c coins that will be unused, but which could be added to any 40c payment involving 5c coins, from which a 5c coin could then be removed to give 38c. This would violate strong minimality.
4. There is never any point in using 5 10c coins in a payment if there is a 50c coin remaining. Even if the 50c is used later, it could be swapped with the 5 10c that are used now.

Combining the observations and assumptions above yields the following algorithm to determine what to pay in the given week.

1. Check whether the total coins remaining are enough to cover the salary. If not, abort.
2. Start by trying to pay the minimum amount, using a greedy algorithm to allocate the coins.
3. If it is impossible to pay the minimum amount, round up to the next multiple of 5c and try again. Keep rounding up to a multiple of the next coin size until payment is possible.

To speed things up, it is worth exploiting the fact that the set of coins used in one week is likely to the same the next week. Each time a new coin-set is built, some simple calculations show how many weeks it is valid for (i.e. until one of the coins runs out), and this number of weeks can be added straight on to the answer without going through the construction for every week.

Here is the solution Croatian senior Jurica Cerovec:

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream in ("allow.in");
ofstream out("allow.out");
int n,c;
vector <pair <int, int> > coins;

int main() {
    in >> n >> c;
    coins.clear();
    for (int i = 0; i<n; i++) {
        int a, b;
        in >> a >> b;
        coins.push_back (make_pair (a, b));
    }
    sort (coins.begin(), coins.end());
    bool moze=true;
    int w=0;

    while (moze) {
          int suma = c;
          moze = false;
          for (int i = coins.size()-1; i >= 0; i--) {
              while (coins[i].second>0 && suma-coins[i].first >= 0) {
                    coins[i].second--;
                    suma -= coins[i].first;
              }
          }
          for (int i = 0; i < coins.size (); i++)
              if (coins[i].second > 0 && suma > 0) {
                 coins[i].second--;
                 suma -= coins[i].first;
                 break;
              }
          if (suma <= 0) moze=true;
          if (moze) w++;
    }
    out << w << endl;
    return 0;
}