Algoritmus
Első feladat, hogy meghatározzuk, hogy mennyinek kéne lennie mindegyikben: $\frac{T_1+T_2+T_3}{3} = D$. Tehát az $i.$ edénybe $D-T_i$-t kell tölteni (ha ez negatív, akkor elvenni). Két edényünk van: $A$ és $B$ (és legyen $A < B$). Ekkor a következő egyenletek megoldásait keressük:
$D - T_i = A\cdot x_i + B\cdot y_i$
Ahol $|x_i|+|y_i|$ minimális, hiszen ez fejezi ki az áttöltést. Mivel $A < B$, ezért ha $x_i$-t futtatjuk 0-tól $\pm \infty$-ig, akkor ha találunk egy $y_i$-t ami jó, akkor az minimális átöntés. Nyílván ezt két edényre tudjuk kiszámolni a harmadik pedig már az eddigiekből következik: $x_3 = -(x_1+x_2)$, illetve $y_3 = -(y_1+y_2)$, hiszen ha mindháromra számolunk egy minimálist, az lehet, hogy nem megvalósítható, de ha kettőre minimális, akkor mindháromra az.
Ha megvan mindhárom edényre, hogy hány kancsó $A$ (azaz $x_1, x_2 \mbox{, és } x_3$), illetve hány kancsó $B$ (azaz $y_1, y_2 \mbox{, és } y_3$) tejet kell beletölteni, vagy áttölteni egy másikba, akkor már csak elvégezzük ezeket az áttöltéseket, először az egyik utána a másik kancsóval. Ami a következőképpen néz ki: keresünk olyan edényt, amibe kéne tölteni valamennyi tejet ($x_i > 0$): keresünk hozzá egy olyat, ahonnan ezt ki kéne tölteni ($x_j < 0$), és elvégezzük az áttöltést ($x_i = x_i +1 \mbox{ illetve } x_j = x_j - 1$), amit megjegyzünk. Ezt addig csináljuk, amíg minden $i$-re $x_i = 0$, majd ugyanezt megcsináljuk $y_i$-vel.
Kódok
Főoldal
>
Versenyek
>
Nemes Tihamér OKSzTV
>
2008
>
Második forduló
>
11-13. osztály
>
Kimérés
>
Megoldás
