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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: