USACO Bronze 2016 February - Milk Pails

Authors: Danh Ta Chi Thanh, Ryan Chou, Rameez Parwez

Appears In

Bronze - Basic Complete Search

Explanation

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

Implementation

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

C++

#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;

int main() {
	freopen("pails.in", "r", stdin);
	int buck1, buck2;
	int order;

Java

import java.io.*;
import java.util.*;

public class Pails {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new FileReader("pails.in"));
		StringTokenizer input = new StringTokenizer(read.readLine());
		read.close();

		int buck1 = Integer.parseInt(input.nextToken());

Python

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!