Category Archives: Sec3.3

USACO 3.3.2 – Special Offers

#include <iostream>
#include <cstdio>
#include <algorithm>
struct offer {
	int N, c, p[5], a[5];
} offers[100];
int id[5], c[5] = { 0 }, num[5], map[1001];
int dp[6][6][6][6][6]={{{{{0}}}}}, O,N,i,j,valid=1,T=0,best=0;
using namespace std;

int main() {
	freopen("shopping.in", "r", stdin), freopen("shopping.out", "w", stdout);

	for (scanf("%d", &O), i = 0; i < O; scanf("%d", &offers[i].c), i++)
		for (j = 0, scanf("%d", &offers[i].N); j < offers[i].N; j++)
			scanf("%d %d", offers[i].p + j, offers[i].a + j);
	for (scanf("%d", &N), i = 0; i < N; map[id[i]] = i, i++)
		scanf("%d %d %d", id + i, num + i, c + i);

	for (int m = 100001, t[5] = { 0 }; m <= 155555; m++, valid =(T = best = 0)+1) {
		for (int n = m; (n / 10) && valid; n /= 10, T++)
			t[T]= n%10, best +=(t[T] * c[T]), valid &= t[T] <= 5;

		if (!valid) continue;

		for (int o = 0; o < O; o++)
			for (int n=0,a[5]={0}, s[5], good = 1; n < offers[o].N; n++) {
				if (map[offers[o].p[n]] != -1)
					a[map[offers[o].p[n]]] = offers[o].a[n];
				for (int q = 0; q < 5; q++)
					good &= t[q] >= a[q], s[q]=t[q]-a[q];
				if (good)
					best = min(best,offers[o].c+dp[s[0]][s[1]][s[2]][s[3]][s[4]]);
			}
		dp[t[0]][t[1]][t[2]][t[3]][t[4]] = best;
	}
	printf("%d\n", dp[num[0]][num[1]][num[2]][num[3]][num[4]]);
}
Advertisements

USACO 3.3.1 – Riding the fences


#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

int start=-1,ct=0,cr[10024]={0},g[501][501]={{0}},deg[501]={0};

void loop(int n) {
	for (int j = 1; j < 501; j++)
		if (g[n][j])
			g[n][j]--, g[j][n]--, loop(j);
	cr[ct++] = n;
}
int main() {
	freopen("fence.in", "r", stdin), freopen("fence.out", "w", stdout);
	int F, a, b, start = 0, mod = 0;
	cin >> F;
	while (F-- && cin >> a >> b)
		g[a][b]++, g[b][a]++, deg[a]++, deg[b]++;
	for (int i = 500; i >= 0; i--)
		mod = deg[i] % 2 ? i : mod, start = deg[i] ? i : start;
	loop(mod ? mod : start);
	for (int c = ct - 1; c >= 0; c--)
		cout << cr[c] << endl;
	return 0;
}