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()