该文档是ACM真题
采取3种行动方式:
(1)你可以让一个罐子装满水
(2)你可以让一个装水的罐子变空
(3)你可以将水从一个罐子里注入另一个罐子。将水从一个罐子注入到另一个罐子时,当第一个罐子已经空了或者第二个罐子已经满了的时候,注入行动就必须停止,例如,如果A的容积为5加仑且装有5加仑的水而B的容积为8加仑但只装了6加仑的水,此时若将A罐子的水注入到B罐,当B罐子装满水的时候行动停止,此时A罐子中还余下3加仑的水。
这个问题由一个三元组给出(Ca,Cb,N),其中,Ca和Cb分别代表罐A和罐B的容积,N最终想要得到的水的体积。采用连续的步骤使得恰好有N加仑的水存在于罐B中,其中一个可能的步骤如下: fill A fill B empty A empty B pour A B pour B A success
其中"pour A B"表示“将罐A中的水倒进罐B中”,"success"表示目标已经达到。
你应该确定你给出的输入是否有解决方案。
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: Ca, Cb, and N. Ca and Cb are the capacities of jugs A and B, and N is the goal. You can assume 0 < Ca <= Cb and N <= Cb <=1000 and that A and B are relatively prime to one another.
Output
Output from your program will consist of a series of instructions from the list of the potential output lines which will result in either of the jugs containing 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 should be no empty lines nor any trailing spaces.
Sample Input
3 5 4 5 7 3
热门文档