USACO 4.1 Beef McNuggests

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

using namespace std;

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int N;
vector<int> vals;

int main() {
    ifstream fin("nuggets.in");
    ofstream fout("nuggets.out");

    fin >> N;
    if (N == 1) {
        cout << 0 << endl;
        fout << 0 << endl;
    }
    vals = vector<int>(N, 0);
    for (int i = 0; i < N; ++i) {
        fin >> vals[i];
    }
    int n = vals[0];
    for (int i = 1; i < N; ++i) {
        n = gcd(n, vals[i]);
        if (n == 1) {
           break;
        }
    }
    if (n != 1) {
        cout << 0 << endl;
        fout << 0 << endl;
        return 0;
    }

    sort(vals.begin(), vals.end());
    int max = vals[N - 1] * vals[N - 2] * gcd(vals[N - 1], vals[N - 2]);
    vector<bool> dp(max, false);
    dp[0] = true;
    for (int i = 0; i < N; ++i) {
        for (int j = vals[i]; j <= max; ++j) {
            if(dp[j - vals[i]]) {
               dp[j] = true;
            }
        }
    }

    for (int i = max; i > 0; --i) {
        if (!dp[i]) {
            cout << i << endl;
            fout << i << endl;
            return 0;
        }
    }
    return 0;
}

2016-12-16

USACO

USACO 3.4 Raucous Rockers

Typical BackPack problem but with the limited scale of test data, a straight forward brutal force search could do it. The search space is the permutation of subsets of all songs, for each song we have two choice - choose or not choose. Iterate the sequence under the constraint of ordering.

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

using namespace std;

int N /* songs */, M /* disks */, T /* disk capacity */;
vector<int> songs;
vector<int> disks;

int main() {
    ifstream fin("rockers.in");
    ofstream fout("rockers.out");
    fin >> N >> T >> M;
    songs = vector<int>(N, 0);
    for (int i = 0; i < N; ++i) {
        fin >> songs[i];
    }
    disks = vector<int>(M, 0);
    int ans = INT_MIN;
    int upper = 1 << N;
    for (int i = 1; i <= upper; ++i) {
        std::fill(disks.begin(), disks.end(), 0);
        int idx = 0, sum = 0;
        for (int j = 0; j < N; ++j) {
            bool pick = (1 << j) & i;
            if (!pick) continue;
            for(int k = idx; k < M; ++k, ++idx){
                if(disks[k] + songs[j] <= T){
                    disks[k] += songs[j];
                    ++sum;
                    break;
                }
            }
        }
        ans = std::max(ans, sum);
    }
    
    cout << ans << endl;
    fout << ans << endl;
}

2016-12-14

USACO

USACO 3.4 Electric Fence

Pick’s Theorem

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

using namespace std;

int gcd(int a, int b) {
    if (b == 0) return a;
    a %= b;
    return gcd(b, a);
}

int n, m, p;
int main() {
    ifstream fin("fence9.in");
    ofstream fout("fence9.out");
    fin >> n >> m >> p;
    int ret = p * m / 2.0 - (gcd(m, n) + gcd(m, abs(p - n)) + p) / 2.0 + 1;
    cout << ret << endl;
    fout << ret << endl;
}