USACO 2.3.5 – Controlling Companies

#include <cstdio>

int main() {
	int N,a,b,p,f=1,g[101][101]={{0}},t[101][101]={{0}},v[101][101]={{0}};
	freopen("concom.in", "r", stdin), freopen("concom.out", "w", stdout);
	scanf("%d", &N);
	for (int i = 0; i < N; g[a][b] = t[a][b] = p, i++)
		scanf("%d %d %d", &a, &b, &p);

	while (f--)
		for (int i = 1; i <= 100; i++)
			for (int j = 1; j <= 100; j++)
				if (t[i][j] >= 50 && !v[i][j]++)
					for (int k = 1; k <= 100; k++)
						if (g[j][k])
							t[i][k] += g[j][k], f=1;

	for (int i = 1; i <= 100; i++)
		for (int j = 1; j <= 100; j++)
			if (i != j && t[i][j] >= 50)
				printf("%d %d\n", i, j);

	return 0;
}

			

			
					

USACO 2.3.4 – Money System

#include <cstdio>
using namespace std;

int main() {
	long long int N, V, v[26] = { 0 }, dp[10001] = { 0 }, i;
	freopen("money.in", "r", stdin), freopen("money.out", "w", stdout);
	scanf("%lld %lld", &V, &N);
	for (i = 0, dp[0] = 1; i < V; i++)
		scanf("%lld", v + i);

	for (int m = 0; m < V; m++)
		for (int n = 0; n <= N; n++)
			dp[n] += (n - v[m] >= 0 ? dp[n - v[m]] : 0);

	printf("%lld\n", dp[N]);
	return 0;
}


		
	
		

USACO 2.3.3 – Zero Sum

#include <cstdio>
#include <iostream>
#include <vector>
#include <stack>
#include <sstream>
char sign[4] = "-+ ";
using namespace std;

int main() {
	int N;
	freopen("zerosum.in", "r", stdin), freopen("zerosum.out", "w", stdout);
	scanf("%d", &N);
	stack<vector<int> > st; st.push(vector<int>());
	while (st.size()) {
		vector<int> s = st.top();
		st.pop();
		if (int(s.size()) < N - 1){
			for (int i = 0; i < 3; i++) {
				vector<int> t = s; t.push_back(i); st.push(t);
			}
			continue;
		}
		int n = 1, sum = 0;
		stringstream line;
		line << 1;
		for (int i = 0; i < int(s.size()); i++) {
			if (s[i] == 2)  n = n * 10 +  (n > 0 ? 1 : -1)*(i+2);
			if (s[i] == 1)  sum += n, n = i + 2;
			if (s[i] == 0)  sum += n, n = -i - 2;
			line << sign[s[i]] << int(i + 2);
		}
		if (sum + n == 0)
			puts(line.str().c_str());
	}
	return 0;
}

		

USACO 2.3.2 – Cow Pedigrees

#include <cstdio>
#include <iostream>

using namespace std;

int main() {
	int dp[101][202]={{0}}, N, K;
	freopen("nocows.in", "r", stdin), freopen("nocows.out", "w", stdout);
	scanf("%d %d", &N, &K);

	for(int i=1; i<=K; i++)
		dp[i][0] = dp[i][1] = 1;

	for(int h=1; h<=K; h++)
		for(int n=1; n<=N; n+=2)
			for(int c=1; c<n; c+=2)
				dp[h][n] = (dp[h][n] + dp[h-1][c]*dp[h-1][n-c-1])%9901;

	cout << (dp[K][N] - dp[K-1][N] + 9901)%9901 << endl;
	return 0;
}

		

USACO 2.3.1 – The Longest Prefix

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>

using namespace std;

int main() {
	int best = -1, n = -1, v[200001] = { 0 }, sz[202];
	char pre[202][11], s[200002], t[80];
	freopen("prefix.in", "r", stdin), freopen("prefix.out", "w", stdout);

	do {
		scanf("%s", pre[++n]);
		sz[n] = strlen(pre[n]);
	} while (pre[n][0] != '.');
	while (scanf("%s", t) != -1)
		strncat(s, t, sizeof t);
	
	stack<int> stk; stk.push(0); v[0] = 1;
	
	while (stk.size()) {
		int from = stk.top(); stk.pop();
		best = max(best, from);
		for (int i = 0; i < n; i++) 
			if (!strncmp(s + from, pre[i], sz[i]) && !(v[from + sz[i]]++))
				stk.push(from + sz[i]);
	}
	printf("%d\n", best);
	return 0;
}