Котлы

From

Max Alekseyev (2:5015/60)

To

Anton Kuznetsov

Date

2002-11-12T14:25:04Z

Area

RU.ALGORITHMS

████ OS/2        Hi, Anton !

Replying to a message of Anton Kuznetsov to All:

 AK>  Дано N котлов размерами А1, А2, А3... Аn литров + есть бесконечный
 AK> котел с водой. Из большого котла можно зачерпывать котлы только
 AK> целиком, а вокогда переливают воду из котла Ai в Aj, то продолжается
 AK> это до тех пор пока во втором котле есть куда воду пихать и пока есть
 AK> откуда воду брать...

 AK>  Вообщем вопрос такой можно ли набрать M литров?

Вот решение для двух котлов:

===cut===
var n,m,k,x,u,v:longint;
    a,a2,b,b2,t:longint;
    j1,j2:char;

begin
write('Input A B M = '); readln(n,m,k);
v:=m; x:=n; a:=1; a2:=0; b:=0; b2:=1;
repeat
  u:=x; t:=v div x; x:=v mod x; v:=u;
  u:=a2; a2:=a-t*a2; a:=u;
  u:=b2; b2:=b-t*b2; b:=u;
until x=0;
{ we got v = gcd(n,m) = a*m + b*n }
if k mod v<>0 then
begin
  writeln('Impossible!');
  halt;
end;
a:=a*k div v; b:=b*k div v;
if a<0 then
begin
  t:=(abs(a)+n-1) div n; inc(a,t*n); dec(b,t*m);
end;
t:=a div n; dec(a,t*n); inc(b,t*m);
if abs(a)+abs(b)<=(n+m) shr 1 then
begin
  j1:='A'; j2:='B';
end else
begin
  j1:='B'; j2:='A';
  u:=m; m:=n; n:=u;
end;

v:=0;
repeat
  writeln('Fill up jug ',j2);
  u:=m;
  repeat
    writeln('Pour water from jug ',j2,' into jug ',j1);
    if u+v>n then begin dec(u,n-v); v:=n end
             else begin inc(v,u); u:=0 end;
    if u=k then
    begin
      writeln('Well done! There are exactly ',k,' liters in jug B.');
      halt;
    end;
    if v=n then
    begin
      writeln('Empty jug ',j1);
      v:=0;
    end;
  until u=0;
until 0<>0;

end.
===cut===

Regards,      °°
        Max    ~

--- FleetStreet 1.27.3.8
 * Origin:  (2:5015/60)