Table of Contents

ExplanationImplementation

Official Analysis (Java)

Explanation

Since the constraints are small, we can use brute force to check all possible combinations by trying every possible number of XX pours and, for each, every possible number of YY pours. In this way we can also keep track of the maximum amount of milk to add to the pail.

Implementation

Time Complexity: O(M2)\mathcal{O}(M^2)

with open("pails.in") as fin:
	buck1, buck2, order = map(int, fin.readline().split())


closest = 0
# Try all possible combinations of the first & second bucket.
for first in range(order + 1):
	if buck1 * first > order:
		break
	for second in range(order + 1):
		current = (buck1 * first) + (buck2 * second)
		if current > order:
			break
		closest = max(closest, current)


print(closest, file=open("pails.out", "w"))

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum