Pretraga u širinu (BFS)

Naivno rešenje koristi pretraga u širinu (BFS) nad prostorom stanja, gde je svako stanje par \((x, y)\) koji predstavlja trenutnu količinu vode u bokalima. Međutim, ovaj pristup može biti neefikasan zbog velikog broja mogućih stanja, posebno kada su kapaciteti bokala veliki.

Linearna Diophantova jednačina

Zadatak se može svesti na rešavanje linearne Diophantove jednačine oblika \(ax + by = c\), gde su \(a\) i \(b\) kapaciteti bokala, a \(c\) željena količina vode. Vrednosti \(x\) i \(y\) predstavljaju broj operacija punjenja (ako su pozitivne) i broj operacija pražnjenja (ako su negativne) za odgovarajuće bokale. Operaciju presipavanja nije potrebno eksplicitno računati, jer ona ne menja ukupnu količinu vode, već samo redistribuira vodu između bokala.

Da bi jednačina imala rešenje, potrebno je da \(c\) bude deljivo sa najvećim zajedničkim deliocem (NZD) brojeva \(a\) i \(b\). Ako NZD ne deli \(c\), onda ne postoji način da se dobije tačno \(c\) litara vode. Za računanje NZD-a možemo koristiti prošireni Euklidov algoritam, koji je efikasan i radi u vremenu \(O(\log(a + b))\). Prošireni Euklidov algoritam nam, pored NZD-a (\(d = \text{NZD}(a, b)\)), takođe, daje vrednosti \(x\) i \(y\) za koje važi

\[ax + by = d.\]

Ukoliko \(c\) nije deljivo sa \(d\), onda nema rešenja i ispisujemo -1. Ako jeste, možemo skalirati rešenje dobijeno proširenim Euklidov algoritmom da bismo dobili rešenje za \(c\):

\[a \cdot x \cdot \frac{c}{d} + b \cdot y \cdot \frac{c}{d} = c.\]

Odnosno, jedno rešenje je dato sa:

\[x_0 = x \cdot \frac{c}{d}, \quad y_0 = y \cdot \frac{c}{d}.\]

Ovo rešenje ne mora biti optimalno, ali nam daje početnu tačku za pronalaženje optimalnog rešenja. Sva rešenja jednačine \(ax + by = c\) su oblika:

\[x = x_0 + k \cdot \frac{b}{d}, \quad y = y_0 - k \cdot \frac{a}{d},\]

gde je \(k\) ceo broj. Naš cilj je da pronađemo takve vrednosti \(x\) i \(y\) koje minimiziraju \(|x| + |y|\), jer to predstavlja minimalan broj operacija punjenja i pražnjenja. Da bismo to postigli, možemo iterirati kroz moguće vrednosti \(k\) i računati odgovarajuće \(x\) i \(y\), dok ne pronađemo minimum. Međutim, postoji efikasniji način da se pronađu optimalna rešenja bez potrebe za iteracijom kroz sve moguće vrednosti \(k\). Naime, želimo da \(x\) i \(y\) budu što bliže nuli, jer to minimizuje broj operacija. Stoga možemo direktno izračunati vrednosti \(k\) koje nam daju rešenja blizu nule i proveriti ta rešenja. Odnosno, tražimo “mala” rešenja za koja važi:

\[|x| < \frac{b}{d} \quad \text{i} \quad |y| < \frac{a}{d}.\]

Dovoljno je da proverimo dva kandidata za \(k\): jedan koji pomera \(x\) ka nuli, i drugi koji pomera \(y\) ka nuli. Onaj koji pomeramo ka nuli možemo pretpostaviti da je pozitivan, a drugi će tada biti negativan (sem u degenerisanim slučajevima kada je \(x = y = 1\) ili \(x + y = 1\)). Odnosno, možemo izračunati:

\[x' = x_0 \pmod{\frac{b}{d}} \quad \text{i} \quad y' = \frac{c - a \cdot x'}{b};\]

\[y'' = y_0 \pmod{\frac{a}{d}} \quad \text{i} \quad x'' = \frac{c - b \cdot y''}{a}.\]

Na kraju, minimalan broj operacija punjenja i pražnjenja biće \(\min\{|x'| + |y'|, |x''| + |y''|\}\). Ako oba rešenja daju isti broj operacija, možemo izabrati bilo koje od njih.

#include <iostream>

using namespace std;

// funkcija koja vraca nzd brojeva a i b i racuna koeficijente x i y
int nzdProsireni(int a, int b, int &x, int &y)
{
   // ako je b jednako 0, onda je nzd(a, b) = a
   if (b == 0) {
      x = 1;
      y = 0;
      return a;
   }

   int x1, y1;
   // rekurzivno resavamo problem za naredna dva elementa u nizu ostataka,
   // a to su brojevi b i a%b
   int nzd = nzdProsireni(b, a % b, x1, y1);
   // azuriramo koeficijente
   x = y1;
   y = x1 - (a / b) * y1;
   return nzd;
}

int min_broj_operacija(int a, int b, int c)
{
   // racunamo nzd brojeva a i b i koeficijente x i y, tako da ax + by = d = nzd(a, b)
   int x, y;
   int d = nzdProsireni(a, b, x, y);

   // ako c nije deljiv sa d, onda nije moguce dobiti c litara vode
   if (c % d != 0) {
      return -1;
   }

   // skaliramo koeficijente x i y tako da dobijemo jedno resenje jednacine ax + by = c
   int x0 = x * (c / d);
   int y0 = y * (c / d);

   // racunamo opsta resenja jednacine ax + by = c
   int korak_a = b / d; // NZD(a, b) | a i b, pa je b/d ceo broj
   int korak_b = a / d; // NZD(a, b) | a i b, pa je a/d ceo broj

   // trazimo dva "mala" resenja, tako da su x i y sto blizi nuli,
   // jer ce nam to dati najmanji broj operacija punjenja i praznjenja

   // trazimo min_x tako da je 0 <= min_x < b/d
   int min_x = (x0 % korak_a + korak_a) % korak_a;
   int min_y = (c - a * min_x) / b;
   
   int min_op = abs(min_x) + abs(min_y);

   // trazimo max_x tako da je 0 <= max_x < a/d
   min_y = (y0 % korak_b + korak_b) % korak_b;
   min_x = (c - b * min_y) / a;

   min_op = min(min_op, abs(min_x) + abs(min_y));

   return min_op;
}


int main() 
{
   int a, b, c; cin >> a >> b >> c;

   cout << min_broj_operacija(a, b, c) << endl;

   return 0;
}