login
A180227
Triangular array T(A,B) read by rows: minimal number of steps required to obtain exactly 1 liter 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.
4
1, 2, -1, 2, 2, -1, 2, -1, 2, -1, 2, 4, 6, 2, -1, 2, -1, -1, -1, 2, -1, 2, 6, 4, 6, 10, 2, -1, 2, -1, 8, -1, 8, -1, 2, -1, 2, 8, -1, 4, 6, -1, 14, 2, -1, 2, -1, 6, -1, -1, -1, 10, -1, 2, -1, 2, 10, 10, 8, 4, 6, 8, 12, 18, 2, -1
OFFSET
1,2
COMMENTS
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 and only if N is a multiple of gcd(A,B).
LINKS
1997 ACM South Central USA programming contest, Problem and Code
Wolfram Mathworld, Three Jug Problem
EXAMPLE
Triangle begins:
1;
2, -1;
2, 2, -1;
2, -1, 2, -1;
2, 4, 6, 2, -1;
2, -1, -1, -1, 2, -1;
2, 6, 4, 6, 10, 2, -1;
2, -1, 8, -1, 8, -1, 2, -1;
2, 8, -1, 4, 6, -1, 14, 2, -1;
2, -1, 6, -1, -1, -1, 10, -1, 2, -1;
CROSSREFS
Sequence in context: A080634 A109925 A306260 * A001468 A014675 A308186
KEYWORD
sign,tabl
AUTHOR
Dmitry Kamenetsky, Aug 17 2010
STATUS
approved