Szczegółowe omówienie zadania Milk Pails:

Link do powyższego omówienia zadania Milk Pails: https://youtu.be/8m6_bOKvzqI?t=1001
Omówienie kodu który zadania Milk Pails: https://youtu.be/8m6_bOKvzqI?t=5350

Link do treści zadania Milk Pails i możliwości umieszczania rozwiązań:
http://www.usaco.org/index.php?page=viewproblem2&cpid=620

Zadanie Milk Pails pokazuje jak stworzyć graf z… wiader: https://youtu.be/8m6_bOKvzqI?t=1754
Stworzony graf jest grafem stanów: https://youtu.be/8m6_bOKvzqI?t=4969
Nasz graf nie ma formalnej reprezentacji: https://youtu.be/8m6_bOKvzqI?t=5053
–
Główny algorytm użyty w zadaniu – BFS: https://youtu.be/8m6_bOKvzqI?t=2384
BFS liczy odległości: https://youtu.be/8m6_bOKvzqI?t=2384
Czy można liczyć odległości DFS-em? https://youtu.be/8m6_bOKvzqI?t=3608
Złożoność BFS: https://youtu.be/8m6_bOKvzqI?t=5242
Kod BFS-a: https://youtu.be/8m6_bOKvzqI?t=5454

–
Zadanie z Amerykańskiej Olimpiady USACO! https://youtu.be/VvJhOAXIQOk?t=156
Pozwala stworzyć fantastyczne CV! https://youtu.be/VvJhOAXIQOk?t=5449

–
Jak się uczyć na podstawie tego zadania? https://youtu.be/QgLyXYmFQeU?t=2019
Pamiętaj by zajrzeć max 1 raz – wtedy się rozwijasz: https://youtu.be/pkLXuuOe_qA?t=3625

Lista zadań z rozwiązaniami: https://oki.org.pl/lista-zadan-materialy.php
Samouczek – przygotowanie do Olimpiad: https://oki.org.pl/tutorial/

Zajęcia: https://oki.org.pl/harmonogram-zajec/
Informacje o zajęciach: https://oki.org.pl/newsletter.php

Warto startować w Olimpiadzie Informatycznej!
https://youtu.be/K7fZfJ8nN6A?t=109

–
Kod C++ programu Milk Pails, który jest omówiony w powyższym filmie i który otrzymuje 100%

–

#include <bits/stdc++.h>
#define fi first
#define se second

using namespace std;

const int MAXN = 100 + 7;

int odleglosc[MAXN][MAXN];
// pojemność pierwszego, drugiego wiadra
int X, Y;

void BFS(pair<int, int> start)
{
	for (int i = 0; i <= X; ++i) {
		for (int j = 0; j <= Y; ++j)
			odleglosc[i][j] = -1;
	}

	queue<pair<int, int>> Q;
	Q.push(start);
	
	odleglosc[start.fi][start.se] = 0;
	while (!Q.empty()) {
		pair<int, int> v = Q.front();
		Q.pop();

		// ile przelejemy z drugiego do pierwszego
		int d21 = min(v.se, X - v.fi);
		// ile przelejemy z pierwszego do drugiego
		int d12 = min(v.fi, Y - v.se);
		pair<int, int> sasiedzi[6] = {
			{X, v.se}, // wypełnij pierwsze wiadro
			{v.fi, Y}, // wypełnij drugie wiadro
			{0, v.se}, // opróżnij pierwsze wiadro
			{v.fi, 0}, // opróżnij drugie wiadro
			{v.fi + d21, v.se - d21}, // drugie -> pierwsze
			{v.fi - d12, v.se + d12}  // pierwsze -> drugie
		};

		for (int i = 0; i < 6; ++i) {
			pair<int, int> u = sasiedzi[i];
			if (odleglosc[u.fi][u.se] != -1)
				continue; // już odwiedzony

			odleglosc[u.fi][u.se] = odleglosc[v.fi][v.se] + 1;
			Q.push(u);
		}
	}
}

int main()
{
	ifstream in("pails.in");
	ofstream out("pails.out");

	int K, M;
	in >> X >> Y >> K >> M;
	BFS({0, 0});

	int wynik = 1e9;
	for (int i = 0; i <= X; ++i) {
		for (int j = 0; j <= Y; ++j) {
			if ((odleglosc[i][j] != -1) && (odleglosc[i][j] <= K))
				wynik = min(abs((i + j) - M), wynik);
		}
	}

	out << wynik << '\n';
	return 0;
}

–
Kod Python programu Milk Pails, który otrzymuje 100%:

from collections import deque

def BFS(start, odleglosc, X, Y):
	Q = deque()
	Q.append(start)
	
	odleglosc[start[0]][start[1]] = 0
	while (len(Q) > 0):
		v = Q.popleft()

		# ile przelejemy z drugiego do pierwszego
		d21 = min(v[1], X - v[0])
		# ile przelejemy z pierwszego do drugiego
		d12 = min(v[0], Y - v[1])
		sasiedzi = [
			[X, v[1]], # wypełnij pierwsze wiadro
			[v[0], Y], # wypełnij drugie wiadro
			[0, v[1]], # opróżnij pierwsze wiadro
			[v[0], 0], # opróżnij drugie wiadro
			[v[0] + d21, v[1] - d21], # drugie -> pierwsze
			[v[0] - d12, v[1] + d12]  # pierwsze -> drugie
		]

		for u in sasiedzi:
			if (odleglosc[u[0]][u[1]] != -1):
				continue # już odwiedzony

			odleglosc[u[0]][u[1]] = odleglosc[v[0]][v[1]] + 1
			Q.append(u)

def solve():
	inp = open("pails.in", "r")

	X, Y, K, M = map(int, inp.readline().split())
	odleglosc = [[-1 for i in range(Y + 1)] for i in range(X + 1)]
	BFS([0, 0], odleglosc, X, Y)

	wynik = 1e9
	for i in range(X + 1): 
		for j in range(Y + 1): 
			if ((odleglosc[i][j] != -1) and (odleglosc[i][j] <= K)):
				wynik = min(abs((i + j) - M), wynik)
		
	

	open("pails.out", "w").write(str(wynik))

solve()