tester-votes.cpp

#include <iostream>
#include <vector>
using namespace std;

struct region {
    int pop, init, delta;
    region() {}
    region(int N, int I, int D) {
        pop = N;
        init = I;
        delta = D;
    }
};

double get_fp(region &r, int m) {
    return double(r.init) + (double(m) / (m + 10.1)) * r.delta; 
}

int round (double f) {
    return int(f + 0.5);
}

int get_votes(region &r, int m) {
    double fp = get_fp(r, m) / 100.0;
    return round(fp * r.pop);
}

int main() {
    int t = 0;
    int n, m;

    while (1) {
        cin >> m >> n;
        if (m == 0 && n == 0) break;
        t++;
        // knapsack where weights are votes and space is money

        vector<vector<int> > dp (m + 1, vector<int> (n, 0));
        vector<region> regions (n);

        for (int i = 0; i < n; i++) {
            int N, I, delta;
            cin >> N >> I >> delta;
            regions[i] = region(N, I, delta);
        }

        // amount of money contributed by each region at each amount
        // helps unroll the DP
        vector<vector<int> > contrib (m + 1, vector<int> (n, 0));

        // knapsack
        for (int M = 0; M <= m; M++)
            dp[M][n - 1] = get_votes(regions[n - 1], M);

        for (int r = n - 2; r >= 0; r--) {
            // do this order to bias in favor of earlier contributions
            for (int M = m; M >= 0; M--) {
                for (int k = 0; k + M <= m; k++) {
                    int current = dp[k][r + 1] + get_votes(regions[r], M);
                    if (current > dp[k + M][r]) {
                        dp[k + M][r] = current;
                        contrib[k + M][r] = M;
                    }
                }
            }
        }

        // get individual contributions from DP
        int money = m;
        vector<int> finalContrib (n, 0);
        for (int r = 0; r < n - 1; r++) {
            finalContrib[r] = contrib[money][r];
            money -= contrib[money][r];
        }
        finalContrib[n - 1] = money;

        cout << "Case " << t << ": " << dp[m][0] << endl;

        for (int r=0; r<n;r++) {
            if (r > 0) cout << " ";
            cout << r << ":" << finalContrib[r];
        }
        cout << endl;
    }
    return 0;
}