USACO Silver 2016 February - Milk Pails

Authors: Óscar Garries, Neo Wang, Nathan Gong, Akshar Yeccherla, George Pong

Edit This Page

Official Analysis

Implementation (DFS)

Time Complexity: O(XYK)\mathcal O(XYK)

C++

#include <bits/stdc++.h>


using namespace std;


bool vis[101][101][101];
int x, y, k, m, sol;


void ff(int curX, int curY, int curK) {
	if (vis[curX][curY][curK] || curK > k) return;
	vis[curX][curY][curK] = true;

Java

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


public class pails {
	static int x, y, k, m, sol;
	static boolean[][][] vis;
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(new File("pails.in"));
		PrintWriter out = new PrintWriter("pails.out");

Python

MAX_OPS = 100


x, y, k, m = map(int, open("pails.in", "r").read().split())


sol = float("inf")
vis = [
	[[False for a in range(MAX_OPS + 1)] for b in range(MAX_OPS + 1)]
	for c in range(MAX_OPS + 1)
]

Alternate Solution: BFS

Time Complexity: O(XY)\mathcal O(XY)

We can directly simulate all operations using BFS.

In this problem, we care about states (i,j)(i, j) where pail XX has ii and pail YY has jj units of milk. We can perform a BFS starting from base state (0,0)(0, 0) to compute dist[i][j]\texttt{dist}[i][j], the minimum number of steps to reach each state. Afterwards, compute the answer by iterating over all states where dist[i][j]≤K\texttt{dist}[i][j] \le K and finding the minimum ∣i+j−M∣|i+j-M|.

For every transition in the BFS, we simulate all possible actions.

  1. Fill either pail completely to the top: set ii to XX or jj to YY.
  2. Empty either pail: set ii or jj to 00.
  3. Pour the contents of one pail into another without overflowing or running out of milk.

To perform operation 3, we can find the amount poured to be min⁡(i,Y−j)\min(i, Y-j) or min⁡(j,X−i)\min(j, X-i) depending on which pail you pour from. Then add/subtract this quantity to each pail appropriately.

Now iterate over all states (i,j)(i, j) where dist[i][j]≤K\texttt{dist}[i][j] \le K and compute the minimum ∣i+j−M∣|i+j-M|.

C++

#include <bits/stdc++.h>


using namespace std;


#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define FORE(i, a, b) for (int i = (a); i <= (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define trav(a, x) for (auto &a : x)


int X, Y, K, M;

Java

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


public class pails {
	final static int MX = 101, INF = (int)1e9 + 7;
	static int X, Y, K, M;
	static int[][] dist;


	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new FileReader("pails.in"));

Python

from collections import deque
import sys


sys.stdin, sys.stdout = open("pails.in", "r"), open("pails.out", "w")
input = sys.stdin.readline




def generate_permutations(p1: int, p2: int):
	# generates results of all possible pours
	da = min(p2, x - p1)  # amount poured when pouring p2 into p1

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