Algorithm 版 (精华区)

发信人: Lerry (life is waiting...), 信区: Algorithm
标  题: 1005P-Jugs-ZJU
发信站: 哈工大紫丁香 (2002年10月07日09:31:54 星期一), 站内信件

Jugs
----------------------------------------------------------------------------
----
Time limit: 1 Seconds   Memory limit: 32768K   Special Judge
Total Submit: 477   Accepted Submit: 181
----------------------------------------------------------------------------
----
In the movie "Die Hard 3", Bruce Willis and Samuel L. Jackson were confronte
d with the following puzzle. They were given a 3-gallon jug and a 5-gallon j
ug and were asked to fill the 5-gallon jug with exactly 4 gallons. This prob
lem generalizes that puzzle.
You have two jugs, A and B, and an infinite supply of water. There are three
 types of actions that you can use: (1) you can fill a jug, (2) you can empt
y a jug, and (3) you can pour from one jug to the other. Pouring from one ju
g to the other stops when the first jug is empty or the second jug is full, 
whichever comes first. For example, if A has 5 gallons and B has 6 gallons a
nd a capacity of 8, then pouring from A to B leaves B full and 3 gallons in 
A.
A problem is given by a triple (Ca,Cb,N), where Ca and Cb are the capacities
 of the jugs A and B, respectively, and N is the goal. A solution is a seque
nce of steps that leaves exactly N gallons in jug B. The possible steps are
fill A
fill B
empty A
empty B
pour A B
pour B A
success
where "pour A B" means "pour the contents of jug A into jug B", and "success
" means that the goal has been accomplished.
You may assume that the input you are given does have a solution.
Input
Input to your program consists of a series of input lines each defining one 
puzzle. Input for each puzzle is a single line of three positive integers: C
a, Cb, and N. Ca and Cb are the capacities of jugs A and B, and N is the goa
l. You can assume 0 < Ca <= Cb and N <= Cb <=1000 and that A and B are relat
ively prime to one another.
Output
Output from your program will consist of a series of instructions from the l
ist of the potential output lines which will result in either of the jugs co
ntaining exactly N gallons of water. The last line of output for each puzzle
 should be the line "success". Output lines start in column 1 and there shou
ld be no empty lines nor any trailing spaces.
Sample Input
3 5 4
5 7 3
Sample Output
fill B
pour B A
empty A
pour B A
fill B
pour B A
success
fill A
pour A B
fill A
pour A B
empty B
pour A B
success
----------------------------------------------------------------------------
----

--
RULE 10 - Television is NOT real life. In real life people 

actually have to leave the coffee shop and go to jobs.

                                             ——Bill Gates

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.249.231]