|
%I #9 Nov 23 2016 23:05:44
%S -1,1,1,2,2,-1,4,2,6,-1,4,2,2,6,-1,4,2,-1,2,6,-1,4,2,8,8,2,6,-1,4,2,4,
%T -1,6,2,6,-1,4,2,-1,10,12,-1,2,6,-1,4,2,10,4,-1,6,12,2,6,-1,4,2,6,12,
%U 10,12,16,10,2,6,-1,4,2,-1,-1,4,-1,6,-1,-1,2,6,-1
%N Triangular array T(A,B) read by rows: minimal number of steps required to obtain exactly 2 liters in jug A (irrespective of jug B), starting with infinite supply of water and two empty jugs with capacities A and B liters. -1 if not possible. A>=B>=1.
%C In the two-jug problem we are given an infinite supply of water and two empty jugs with integer liter capacities A and B, A>=B>=1. We must use the least number of steps to measure exactly N integer liters of water in jug A, irrespective of jug B. Each step is one of the following: empty a jug, fill a jug, or pour from one jug to the other. Pouring stops as soon as the source jug is empty or the destination jug is full. It is known that the amount N can be made if only if N is a multiple of gcd(A,B).
%H Alois P. Heinz, <a href="/A180228/b180228.txt">Rows n = 1..141, flattened</a>
%H 1997 ACM South Central USA programming contest, <a href="http://www.ntnu.edu.tw/acm/ProblemSetArchive/B_US_SouthCen/1997/Jugs.html">Problem and Code</a>
%H Wolfram Mathworld, <a href="http://mathworld.wolfram.com/ThreeJugProblem.html">Three Jug Problem</a>
%e Triangle begins:
%e -1;
%e 1, 1;
%e 2, 2, -1;
%e 4, 2, 6, -1;
%e 4, 2, 2, 6, -1;
%e 4, 2, -1, 2, 6, -1;
%e 4, 2, 8, 8, 2, 6, -1;
%e 4, 2, 4, -1, 6, 2, 6, -1;
%e 4, 2, -1, 10, 12, -1, 2, 6, -1;
%e 4, 2, 10, 4, -1, 6, 12, 2, 6, -1;
%e For example T(4,3) = 6.
%Y Cf. A180227.
%K sign,tabl
%O 1,4
%A _Dmitry Kamenetsky_, Aug 17 2010
|
