|
| |
|
|
A180229
|
|
Triangular array T(A,B) read by rows: minimal number of steps required to obtain exactly 3 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.
|
|
2
|
|
|
|
-1, -1, -1, 1, 1, 1, 2, -1, 2, -1, 4, 2, 2, 6, -1, 6, -1, 2, -1, 10, -1, 6, 4, 2, 2, 6, 10, -1, 6, -1, 2, -1, 2, -1, 10, -1, 6, 6, 2, 8, 8, 2, 10, 10, -1, 6, -1, 2, -1, -1, -1, 2, -1, 10, -1, 6, 8, 2, 4, 14, 14, 6, 2, 14, 10, -1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,7
|
|
|
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
|
|
|
|
EXAMPLE
|
Triangle begins:
-1;
-1,-1;
1, 1, 1;
2, -1, 2, -1;
4, 2, 2, 6, -1;
6, -1, 2, -1, 10, -1;
6, 4, 2, 2, 6, 10, -1;
6, -1, 2, -1, 2, -1, 10, -1;
6, 6, 2, 8, 8, 2, 10, 10, -1;
6, -1, 2, -1, -1, -1, 2, -1, 10, -1;
For example T(5,4) = 6.
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
