Category Archives: USACO

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]]);
}

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;
}

USACO 3.2.6 – Sweet Butter

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
struct E { int b, d; };
int main() {
	freopen("butter.in", "r", stdin), freopen("butter.out", "w", stdout);
	int N, C, P, p[801] = { 0 }, best[801], INF = 10000000, min_r = INF;
	vector<E> e[801]; vector<int> cows;
	fill(e, e + 800, vector<E> ()), fill(best, best + 801, INF);
	scanf("%d %d %d", &N, &P, &C);
	for (int c, i = 0; i < N; p[c]++, cows.push_back(c), i++)
		scanf("%d", &c);
	for (int a, b, d, c = 0; c < C; c++) {
		scanf("%d %d %d", &a, &b, &d);
		e[a].push_back(E { b, d }), e[b].push_back(E { a, d });
	}
	for (int s = 1, r = 0; s <= P; fill(best, best + 801, INF), r = 0, ++s) {
		queue<E> q; q.push(E { s, best[s] = 0 });
		while (q.size()) {
			E f = q.front(); q.pop();
			for (int b = 0; b < e[f.b].size(); ++b) {
				E o = e[f.b][b];
				if (best[o.b] > o.d + best[f.b])
					q.push(E { o.b, (best[o.b] = o.d + best[f.b]) });
			}
		}
		for (int i = 0; i < cows.size(); ++i)
			r += best[cows[i]];
		min_r = r < min_r ? r : min_r;
	}
	printf("%d\n", min_r);
}

USACO 3.2.5 – Magic Squares

#include <cstdio>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
int main() {
	freopen("msquare.in", "r", stdin), freopen("msquare.out", "w", stdout);
	string f="        ", s="12345678",seq,st,en,rev;
	char c; map<string, int> v;

	for(int i=0;i<8;i++,getchar()) f[i]= getchar();

	queue<string> q; q.push(s), q.push("");
	while(q.size()){
		s=q.front(), q.pop(), seq = q.front(), q.pop();
		if(v[s]++) continue;
		if(s==f){
			printf("%d\n%s\n", seq.size(), seq.c_str());
			return 0;
		}
		rev=string(s.rbegin(), s.rend());
		q.push(rev), q.push(seq+'A');

		st=s.substr(0,4),en=s.substr(4,4);
		rotate(st.begin(), st.begin()+3, st.end()),rotate(en.begin(),en.begin()+1,en.end());
		q.push(st+en), q.push(seq+'B');

		c =s[1],s[1]=s[6],s[6]=s[5],s[5]=s[2],s[2]=c;
		q.push(s), q.push(seq+'C');
	}
	puts("NONE");
}

USACO 3.2.4 – Feeding Ratios

#include <cstdio>
#include <cstring>

int main() {
	freopen("ratios.in", "r", stdin), freopen("ratios.out", "w", stdout);
	int r[4][3], ans[4], best = 400, bi = -1, bj = -1, bk= -1, br = -1, ratio;
	for (int i = 0; i < 4; i++)
		scanf("%d %d %d", r[i], r[i] + 1, r[i] + 2);

	for (int i = 0; i < 101; i++)
		for (int j = 0; j < 101; j++)
			for (int k = 0, good = 1; k < 101; good = 1, k++) {
				if (i + j + k < 1) continue;
				for (int m = 0; m < 3; ratio=r[0][m]?ans[m]/r[0][m]:ratio, m++)
					ans[m] = (r[1][m]*i+r[2][m]*j+r[3][m]*k);
				for (int m=0;m<3;m++) good&=(ratio*r[0][m]==ans[m]);
				if (good && i + j + k < best)
					best = i + j + k, bi = i, bj = j, bk = k, br = ratio;
			}

	if (bi == -1) puts("NONE");
	else printf("%d %d %d %d\n", bi, bj, bk, br);
}

USACO 3.2.3 – Spinning Wheels


#include <cstdio>
#include <cstring>

int main() {
	freopen("spin.in", "r", stdin), freopen("spin.out", "w", stdout);
	int v[5], nwidges[5], wd[5][5][2], open[360] = { 0 };
	for (int i = 0; i < 5; i++) {
		scanf("%d %d", v + i, nwidges + i);
		for (int j = 0; j < nwidges[i]; j++)
			scanf("%d %d", wd[i][j], wd[i][j] + 1);
	}
	for (int t = 0; t < 360; memset(open, 0, sizeof open), t++)
		for (int w = 0; w < 5; w++)
			for (int n = 0; n < nwidges[w]; n++)
				for (int p=t*v[w]+wd[w][n][0]; p<=t*v[w]+wd[w][n][0]+wd[w][n][1]; p++) {
					if (++open[p % 360] == 5) {
						printf("%d\n", t);
						return 0;
					}
				}

	puts("none");
}

USACO 3.2.2 – Stringsobits

#include <cstdio>
#include <algorithm>

int main() {
	freopen("kimbits.in", "r", stdin), freopen("kimbits.out", "w", stdout);
	unsigned N, L, I, sum[33][33];
	scanf("%u %u %u", &N, &L, &I);

	for (int i = 0; i < 33; i++)
		for (int j = 0; j < 33; j++)
			sum[i][j] = j && i ? sum[i - 1][j] + sum[i - 1][j - 1] : 1;

	for (int i = N, b = I > sum[i - 1][L]; i >= 1; i--, b = I > sum[i - 1][L])
		putchar('0' + b), I -= b ? sum[i - 1][L] : 0, L -= b;

	putchar('\n');
}

USACO 3.2.1 – Factorials

the max N is 4,200, first truncate all right-most zeros whenever found. then recall the multiplication process, if you multiplied 4,200 by the previous factorial. then the right most digitl will be the result of mutlip. of 4,200 by the last digit of the previous factorial. and since every time you increase the digit index you add a right most zero. then only the last Log_10(4,200) digits should be kept.

#include <cstdio>

int main() {
	freopen("fact4.in", "r", stdin), freopen("fact4.out", "w", stdout);
	int N, f=1;
	scanf("%d", &N);
	for(int i=2; i<=N; f%=10000, i++){
		f*= i;
		while(f%10==0) f/=10;
	}
	printf("%d\n", f%10);
}

USACO 3.1.3 – Shaping Regions

For each new rectangle layer; check the intersection with all previous rectangles which were not cut, divide the rectangle into 4 regions.

  • first case is obvious
  • for all other cases of intersection some of the rectangles will have area 0 being found at the edges of the older rectangle.
    • and thus won’t be calculated.

after cutting a previous layer, mark it as torn so that it won’t be checked for intersection later.


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

struct Rectangle { int ax, ay, bx, by, c; } rec[100001];
int main() {
	freopen("rect1.in", "r", stdin), freopen("rect1.out", "w", stdout);
	int W, H, N, top=0, cut[100000]= {0}, count[2501]={0}, ax, ay, bx, by, c;
	scanf("%d %d %d", &W, &H, &N);

	rec[top++] = Rectangle {0,0,W,H,1};
	for(int i=0; i<N; ++i){
		scanf("%d %d %d %d %d", &ax, &ay, &bx, &by, &c);
		rec[top++]= Rectangle{ax, ay, bx, by, c};
		for(int j=0, J=top-1; j<J; ++j)
			if(!cut[j]){
				int max_ax = max(ax, rec[j].ax), max_ay = max(ay, rec[j].ay);
				int min_bx = min(bx, rec[j].bx), min_by = min(by, rec[j].by);
				if(max_ax >= min_bx || max_ay >= min_by) continue; else cut[j]++;
				rec[top++] = Rectangle { rec[j].ax, rec[j].ay, min_bx   , max_ay   , rec[j].c};
				rec[top++] = Rectangle { min_bx	  , rec[j].ay, rec[j].bx, min_by   , rec[j].c};
				rec[top++] = Rectangle { rec[j].ax, max_ay 	 , max_ax   , rec[j].by, rec[j].c};
				rec[top++] = Rectangle { max_ax	  , min_by	 , rec[j].bx, rec[j].by, rec[j].c};
			}
	}
	for(int i=0; i<top; ++i)
		if(!cut[i])
			count[rec[i].c] += (rec[i].bx- rec[i].ax)*(rec[i].by- rec[i].ay);

	for(int i=1; i<=2500; ++i)
		if(count[i]>0)
			printf("%d %d\n", i, count[i]);
}

USACO 3.1.5 – Contact


/*
 ID: mohmdad5
 PROG: contact
 LANG: C++
 */
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

struct Pattern { int pattern, count; };
bool operator <(const Pattern& a, const Pattern& b) {
	return a.count == b.count ? a.pattern < b.pattern : a.count > b.count;
}
void print(int num) {
	if (num <= 1) return;
	print(num / 2), putchar('0' + (num % 2));
}
int main() {
	freopen("contact.in", "r", stdin), freopen("contact.out", "w", stdout);
	char x[200001];
	int count[20000] = {0}, mask, a, b, n, A_min, B_max, L=1, i, j, top = 0, inLine = 0, N = 0;
	Pattern patterns[20001];
	cin >> a >> b >> n;
	A_min = 1 << (a), B_max = (1 << (b + 1)) - 1;
	while (cin >> x[L])
		L++;

	for (i = 0; i < L; i++)
		for (j = 1, mask = 1L; j <= b && i + j < L; j++)
			mask = (mask << 1) + (x[i + j] - '0'), count[mask] += j >= a;

	for (int i = A_min; i <= B_max; i++)
		if (count[i])
			patterns[top++] = Pattern { i, count[i] };

	sort(patterns, patterns + top);

	printf("%d\n", patterns[0].count), print(patterns[0].pattern);
	for (int i = 1; i < top; i++) {
		if (patterns[i].count != patterns[i - 1].count && !(inLine = 0) && ++N) {
			if (N >= n) break;
			printf("\n%d\n", patterns[i].count);
		} else
			putchar(inLine == 5 ? '\n' : ' '), inLine = (inLine + 1) % 6;
		print(patterns[i].pattern);
	}
	puts("");
}