Milk Pails

Solución en video

Por David Zhou

Código de la solución en video (explicación DFS + BFS; solo código BFS)

C++JavaPython


#include <cmath>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
struct State {
	int op, a, b;
};
 
int main() {
	freopen("pails.in", "r", stdin);
	freopen("pails.out", "w", stdout);
 
	int x, y, k, m;
	cin >> x >> y >> k >> m;
 
	int res = m;  // inicialmente ambos baldes están vacíos, así que hay una diferencia de m-0,
	              // que es m
	vector<vector<int>> visited(x + 1, vector<int>(y + 1, 0));
	visited[0][0] = 1;
 
	queue<State> q;
	q.push({0, 0, 0});
	while (!q.empty()) {
		int op = q.front().op, a = q.front().a, b = q.front().b;
		q.pop();
		res = min(res, abs(m - (a + b)));
		if (op == k) { continue; }
 
		// llenar
		if (visited[x][b] == 0) {
			visited[x][b] = 1;
			q.push({op + 1, x, b});
		}
		if (visited[a][y] == 0) {
			visited[a][y] = 1;
			q.push({op + 1, a, y});
		}
 
		// vaciar
		if (visited[0][b] == 0) {
			visited[0][b] = 1;
			q.push({op + 1, 0, b});
		}
		if (visited[a][0] == 0) {
			visited[a][0] = 1;
			q.push({op + 1, a, 0});
		}
 
		// verter X en Y
		int pour_x = a + b - y;
		if (pour_x <= 0) {
			if (visited[0][a + b] == 0) {
				visited[0][a + b] = 1;
				q.push({op + 1, 0, a + b});
			}
		} else if (visited[pour_x][y] == 0) {
			visited[pour_x][y] = 1;
			q.push({op + 1, pour_x, y});
		}
 
		// verter Y en X
		int pour_y = a + b - x;
		if (pour_y <= 0) {
			if (visited[a + b][0] == 0) {
				visited[a + b][0] = 1;
				q.push({op + 1, a + b, 0});
			}
		} else if (visited[x][pour_y] == 0) {
			visited[x][pour_y] = 1;
			q.push({op + 1, x, pour_y});
		}
	}
 
	cout << res << endl;
}


import java.io.*;
import java.util.*;
 
public class Pails {
	private static class State {
		int op, a, b;
		State(int op, int a, int b) {
			this.op = op;
			this.a = a;
			this.b = b;
		}
	}
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("pails.in"));
		PrintWriter pw =
		    new PrintWriter(new BufferedWriter(new FileWriter("pails.out")));
 
		StringTokenizer st = new StringTokenizer(br.readLine());
		int x = Integer.parseInt(st.nextToken());
		int y = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
 
		int res = m;  // inicialmente ambos baldes están vacíos, así que hay una diferencia de
		              // m-0, que es m
		int[][] visited = new int[x + 1][y + 1];
		visited[0][0] = 1;
 
		Queue<State> q = new LinkedList<>();
		q.add(new State(0, 0, 0));
 
		while (!q.isEmpty()) {
			State cur = q.poll();
			int op = cur.op, a = cur.a, b = cur.b;
			res = Math.min(res, Math.abs(m - (a + b)));
			if (op == k) { continue; }
 
			// llenar
			if (visited[x][b] == 0) {
				visited[x][b] = 1;
				q.add(new State(op + 1, x, b));
			}
			if (visited[a][y] == 0) {
				visited[a][y] = 1;
				q.add(new State(op + 1, a, y));
			}
 
			// vaciar
			if (visited[0][b] == 0) {
				visited[0][b] = 1;
				q.add(new State(op + 1, 0, b));
			}
			if (visited[a][0] == 0) {
				visited[a][0] = 1;
				q.add(new State(op + 1, a, 0));
			}
 
			// verter X en Y
			int pour_x = a + b - y;
			if (pour_x <= 0) {
				if (visited[0][a + b] == 0) {
					visited[0][a + b] = 1;
					q.add(new State(op + 1, 0, a + b));
				}
			} else if (visited[pour_x][y] == 0) {
				visited[pour_x][y] = 1;
				q.add(new State(op + 1, pour_x, y));
			}
 
			// verter Y en X
			int pour_y = a + b - x;
			if (pour_y <= 0) {
				if (visited[a + b][0] == 0) {
					visited[a + b][0] = 1;
					q.add(new State(op + 1, a + b, 0));
				}
			} else if (visited[x][pour_y] == 0) {
				visited[x][pour_y] = 1;
				q.add(new State(op + 1, x, pour_y));
			}
		}
 
		pw.println(res);
		pw.close();
		br.close();
	}
}


from collections import deque
 
 
def main():
	with open("pails.in", "r") as fin:
		x, y, k, m = map(int, fin.readline().split())
 
	# inicialmente ambos baldes están vacíos, así que hay una diferencia de m-0, que es m
	res = m
	visited = [[0] * (y + 1) for _ in range(x + 1)]
	visited[0][0] = 1
 
	q = deque()
	q.append((0, 0, 0))  # (op, a, b)
 
	while q:
		op, a, b = q.popleft()
		res = min(res, abs(m - (a + b)))
		if op == k:
			continue
 
		# llenar
		if visited[x][b] == 0:
			visited[x][b] = 1
			q.append((op + 1, x, b))
		if visited[a][y] == 0:
			visited[a][y] = 1
			q.append((op + 1, a, y))
 
		# vaciar
		if visited[0][b] == 0:
			visited[0][b] = 1
			q.append((op + 1, 0, b))
		if visited[a][0] == 0:
			visited[a][0] = 1
			q.append((op + 1, a, 0))
 
		# verter X en Y
		pour_x = a + b - y
		if pour_x <= 0:
			if visited[0][a + b] == 0:
				visited[0][a + b] = 1
				q.append((op + 1, 0, a + b))
		else:
			if visited[pour_x][y] == 0:
				visited[pour_x][y] = 1
				q.append((op + 1, pour_x, y))
 
		# verter Y en X
		pour_y = a + b - x
		if pour_y <= 0:
			if visited[a + b][0] == 0:
				visited[a + b][0] = 1
				q.append((op + 1, a + b, 0))
		else:
			if visited[x][pour_y] == 0:
				visited[x][pour_y] = 1
				q.append((op + 1, x, pour_y))
 
	print(res, file=open("pails.out", "w"))
 
 
main()

Análisis oficial (Java)

Solución 1 (DFS)

Explicación

Podemos hacer un DFS empezando desde el estado base $(0, 0)$ , donde ambos baldes tienen $0$ unidades de leche.

Notemos que necesitamos usar una grilla 3D para rastrear correctamente los estados visitados. Esto es porque el DFS puede visitar el mismo estado $(i, j)$ más temprano en su procesamiento pero a través de un mayor número de operaciones. Para rastrear bien las celdas visitadas, hay que asegurarse de que la grilla de visitados tenga un registro de cuántas operaciones tomó alcanzar cada estado cada vez.

Simular las seis operaciones cada vez alcanza para pasar las restricciones.

Implementación

Complejidad temporal: $\mathcal O(XYK)$

C++JavaPython


#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;
 
	sol = min(sol, abs(m - (curX + curY)));
	// caso 1
	ff(x, curY, curK + 1);
	ff(curX, y, curK + 1);
	// caso 2
	ff(0, curY, curK + 1);
	ff(curX, 0, curK + 1);
	// caso 3
	int leftoverX = (curX + curY > y ? curX + curY - y : 0);
	int leftoverY = (curY + curX > x ? curY + curX - x : 0);
 
	ff(leftoverX, min(y, curY + curX), curK + 1);
	ff(min(x, curX + curY), leftoverY, curK + 1);
}
 
int main() {
	freopen("pails.in", "r", stdin);
	freopen("pails.out", "w", stdout);
 
	cin >> x >> y >> k >> m;
	sol = m;
	ff(0, 0, 0);
	cout << sol << '\n';
}


import java.io.*;
import java.util.*;
 
public class Pails {
	static class State {
		int op, a, b;
 
		State(int op, int a, int b) {
			this.op = op;
			this.a = a;
			this.b = b;
		}
	}
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("pails.in"));
		PrintWriter pw =
		    new PrintWriter(new BufferedWriter(new FileWriter("pails.out")));
 
		StringTokenizer st = new StringTokenizer(br.readLine());
		int x = Integer.parseInt(st.nextToken());
		int y = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
 
		int res = m;  // inicialmente ambos baldes están vacíos, así que hay una diferencia de
		              // m-0, que es m
		int[][] visited = new int[x + 1][y + 1];
		visited[0][0] = 1;
 
		Queue<State> q = new LinkedList<>();
		q.add(new State(0, 0, 0));
 
		while (!q.isEmpty()) {
			State cur = q.poll();
			int op = cur.op, a = cur.a, b = cur.b;
			res = Math.min(res, Math.abs(m - (a + b)));
			if (op == k) { continue; }
 
			// llenar
			if (visited[x][b] == 0) {
				visited[x][b] = 1;
				q.add(new State(op + 1, x, b));
			}
			if (visited[a][y] == 0) {
				visited[a][y] = 1;
				q.add(new State(op + 1, a, y));
			}
 
			// vaciar
			if (visited[0][b] == 0) {
				visited[0][b] = 1;
				q.add(new State(op + 1, 0, b));
			}
			if (visited[a][0] == 0) {
				visited[a][0] = 1;
				q.add(new State(op + 1, a, 0));
			}
 
			// verter X en Y
			int pour_x = a + b - y;
			if (pour_x <= 0) {
				if (visited[0][a + b] == 0) {
					visited[0][a + b] = 1;
					q.add(new State(op + 1, 0, a + b));
				}
			} else if (visited[pour_x][y] == 0) {
				visited[pour_x][y] = 1;
				q.add(new State(op + 1, pour_x, y));
			}
 
			// verter Y en X
			int pour_y = a + b - x;
			if (pour_y <= 0) {
				if (visited[a + b][0] == 0) {
					visited[a + b][0] = 1;
					q.add(new State(op + 1, a + b, 0));
				}
			} else if (visited[x][pour_y] == 0) {
				visited[x][pour_y] = 1;
				q.add(new State(op + 1, x, pour_y));
			}
		}
 
		pw.println(res);
		pw.close();
		br.close();
	}
}


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)
]
 
 
def ff(cur_x: int, cur_y: int, cur_k: int) -> int:
	global sol
 
	if cur_k > k or vis[cur_x][cur_y][cur_k]:
		return
 
	vis[cur_x][cur_y][cur_k] = True
	sol = min(sol, abs(m - (cur_x + cur_y)))
 
	# caso 1
	ff(x, cur_y, cur_k + 1)
	ff(cur_x, y, cur_k + 1)
 
	# caso 2
	ff(0, cur_y, cur_k + 1)
	ff(cur_x, 0, cur_k + 1)
 
	# caso 3
	if cur_x > y - cur_y:
		ff(cur_x - y + cur_y, y, cur_k + 1)
	else:
		ff(0, cur_y + cur_x, cur_k + 1)
 
	if cur_y > x - cur_x:
		ff(x, cur_y - x + cur_x, cur_k + 1)
	else:
		ff(cur_x + cur_y, 0, cur_k + 1)
 
 
ff(0, 0, 0)
print(sol, file=open("pails.out", "w"))

Solución 2 (BFS)

Explicación

Podemos simular directamente todas las operaciones usando BFS.

En este problema, nos importan los estados $(i, j)$ donde el balde $X$ tiene $i$ y el balde $Y$ tiene $j$ unidades de leche. Podemos hacer un BFS empezando desde el estado base $(0, 0)$ para computar $\texttt{dist}[i][j]$ , el número mínimo de pasos para alcanzar cada estado. Después, computamos la respuesta iterando sobre todos los estados donde $\texttt{dist}[i][j] \le K$ y hallando el mínimo $|i+j-M|$ .

Para cada transición del BFS, simulamos todas las acciones posibles.

Llenar cualquiera de los baldes hasta arriba: poner $i$ en $X$ o $j$ en $Y$ .
Vaciar cualquiera de los baldes: poner $i$ o $j$ en $0$ .
Verter el contenido de un balde en el otro sin desbordar ni quedarse sin leche.

Para realizar la operación 3, podemos hallar la cantidad vertida como $\min(i, Y-j)$ o $\min(j, X-i)$ según de qué balde se vierta. Luego sumamos/restamos esta cantidad a cada balde de forma apropiada.

Ahora iteramos sobre todos los estados $(i, j)$ donde $\texttt{dist}[i][j] \le K$ y computamos el mínimo $|i+j-M|$ .

Implementación

Complejidad temporal: $\mathcal O(XY)$

C++JavaPython


#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;
 
const int MX = 101;
const int INF = 1e9 + 7;
 
int dist[MX][MX];
 
void setIn(string s) { freopen(s.c_str(), "r", stdin); }
void setOut(string s) { freopen(s.c_str(), "w", stdout); }
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
 
	setIn("pails.in");
	setOut("pails.out");
 
	cin >> X >> Y >> K >> M;
 
	F0R(i, MX) F0R(j, MX) dist[i][j] = INF;
 
	queue<pair<int, int>> bfs;
	bfs.push({0, 0});
	dist[0][0] = 0;
 
	while (!bfs.empty()) {
		pair<int, int> top = bfs.front();
		bfs.pop();
		int ndist = dist[top.first][top.second] + 1;
 
		int pourX = min(top.first, Y - top.second);
		int pourY = min(top.second, X - top.first);
 
		int nx[] = {top.first,        0, X, top.first, top.first - pourX,
		            top.first + pourY};  // todos los vertidos posibles
		int ny[] = {0, top.second,         top.second,
		            Y, top.second + pourX, top.second - pourY};
 
		F0R(i, 6) {
			if (ndist > K || dist[nx[i]][ny[i]] != INF) continue;
			dist[nx[i]][ny[i]] = ndist;
			bfs.push({nx[i], ny[i]});
		}
	}
 
	int ret = INF;
 
	F0R(i, MX) {
		F0R(j, MX) {
			if (dist[i][j] <= K) ret = min(ret, abs(i + j - M));
		}
	}
 
	cout << ret << endl;
}


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"));
		PrintWriter writer = new PrintWriter("pails.out");
 
		StringTokenizer st = new StringTokenizer(reader.readLine());
		X = Integer.parseInt(st.nextToken());
		Y = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
 
		dist = new int[MX][MX];
		for (int i = 0; i <= X; ++i)
			for (int j = 0; j <= Y; ++j) dist[i][j] = INF;
 
		Queue<Pair<Integer, Integer>> bfs = new ArrayDeque<>();
		bfs.add(new Pair<Integer, Integer>(0, 0));
		dist[0][0] = 0;
 
		while (!bfs.isEmpty()) {
			Pair<Integer, Integer> top = bfs.poll();
			int ndist = dist[top.first][top.second] + 1;
 
			int pourX = Math.min(top.first, Y - top.second);
			int pourY = Math.min(top.second, X - top.first);
 
			// las 6 formas posibles de verter
			int nx[] = {top.first,        0, X, top.first, top.first - pourX,
			            top.first + pourY};
			int ny[] = {0, top.second,         top.second,
			            Y, top.second + pourX, top.second - pourY};
 
			for (int i = 0; i < 6; ++i)
				if (ndist < dist[nx[i]][ny[i]]) {
					dist[nx[i]][ny[i]] = ndist;
					bfs.add(new Pair<Integer, Integer>(nx[i], ny[i]));
				}
		}
 
		int ret = INF;
		for (int i = 0; i <= X; ++i)
			for (int j = 0; j <= Y; ++j)
				if (dist[i][j] <= K) ret = Math.min(ret, Math.abs(i + j - M));
		writer.println(ret);
 
		reader.close();
		writer.close();
	}
 
	static class Pair<U, V> {
		public U first;
		public V second;
		Pair(U first, V second) {
			this.first = first;
			this.second = second;
		}
	}
}


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):
	# genera los resultados de todos los vertidos posibles
	da = min(p2, x - p1)  # cantidad vertida al verter p2 en p1
	db = min(p1, y - p2)  # cantidad vertida al verter p1 en p2
	return [(x, p2), (p1, y), (0, p2), (p1, 0), (p1 + da, p2 - da), (p1 - db, p2 + db)]
 
 
x, y, k, m = map(int, input().split())
 
dist = [[-1] * (y + 1) for _ in range(x + 1)]
dist[0][0] = 0
 
min_diff = float("inf")
 
queue = deque([(0, 0)])
while queue:
	p1, p2 = queue.pop()
	curr_dist = dist[p1][p2]
 
	if curr_dist >= k:
		break
 
	for n1, n2 in generate_permutations(p1, p2):
		if dist[n1][n2] == -1:
			dist[n1][n2] = curr_dist + 1
			queue.appendleft((n1, n2))
 
			diff = abs(n1 + n2 - m)
			if diff < min_diff:
				min_diff = diff
 
print(min_diff)

Solución 3 (DP)

Explicación

Los estados de este problema son una combinación de las cantidades de leche en cada balde y el número de operaciones para alcanzar tales cantidades.

Sea $\text{f}[i][j][l]$ si es posible alcanzar cantidades $i$ y $j$ en los baldes en $l$ operaciones. Nuestro caso base es $\text{f}[0][0][0]$ como verdadero, ya que inicialmente no hay leche. Ahora, iteramos sobre todos los $l$ tales que $0\leq l<K$ , y todos los $i$ y $j$ posibles. Para cualquier estado verdadero $\text{f}[i][j][l]$ , marcamos $\text{f}[i'][j'][l+1]$ como verdadero para todos los $(i', j')$ que pueden resultar de una sola operación basada en $(i, j)$ . Las operaciones posibles se explican en las soluciones anteriores.

La respuesta es el mínimo de $|i+j-m|$ para todos los $\texttt{f}[i][j][l]$ verdaderos.

Implementación

Complejidad temporal: $\mathcal O(XYK)$

C++


#include <climits>
#include <fstream>
#include <vector>
using namespace std;
 
int main() {
	ifstream fin("pails.in");
 
	int x, y, k, m;
	fin >> x >> y >> k >> m;
 
	// f[i][j][l] = si las cantidades (i, j) en l pasos son posibles
	vector f(x + 1, vector(y + 1, vector<int>(k + 1)));
 
	// estado base: no hay leche en 0 pasos
	f[0][0][0] = 1;
 
	// usamos cada capa de DP para calcular la siguiente
	for (int l = 0; l < k; l++) {
		for (int i = 0; i <= x; i++) {
			for (int j = 0; j <= y; j++) {
				if (f[i][j][l]) {
					f[i][0][l + 1] = 1;
					f[0][j][l + 1] = 1;
					f[i][y][l + 1] = 1;
					f[x][j][l + 1] = 1;
 
					// Verter de i a j
					{
						int amount_poured = min(y - j, i);
						f[i - amount_poured][j + amount_poured][l + 1] = 1;
					}
 
					// Verter de j a i
					{
						int amount_poured = min(x - i, j);
						f[i + amount_poured][j - amount_poured][l + 1] = 1;
					}
				}
			}
		}
	}
 
	// Recorremos todos los estados verdaderos y computamos la respuesta.
	int ans = INT_MAX;
	for (int l = 0; l <= k; l++) {
		for (int i = 0; i <= x; i++) {
			for (int j = 0; j <= y; j++) {
				if (f[i][j][l]) { ans = min(ans, abs(i + j - m)); }
			}
		}
	}
 
	ofstream fout("pails.out");
	fout << ans << endl;
}