七、無刻度容器倒水問題 ( 20分 )

    給定兩個容量分別為x公升和y公升的無刻度容器，若只能將容器完全裝滿、完全倒光或將水倒到另外的容器中，要設法量出z公升的水最少需要多少次? (裝滿、倒光、倒到另一個容器各算一次)，若無法倒出z公升的水則輸出-1。假設處理過程中水量不損耗，水無限供應。

    假設以序對 (x, y) 代表目前容量。若x=3, y=5, z=4，則其可能的動作如下：(1)先把三公升容器的水加滿 (3, 0), (2)將三公升容器中的水倒入五公升的容器內，這時五公升容器內有3公升水 (0, 3)。(3)再次把三公升的水加滿變成 (3, 3)，(4)再將三公升容器中的水倒入五公升倒滿五公升的容器內，五公升容器裝滿5公升水，而這時三公升容器內的水應該還剩下1公升 (1, 5)，(5) 請把五公升容器內的水全倒掉 (1, 0)，(6)再將三公升容器內的所剩1公升水倒入五公升容器內 (0, 1)，(7) 再一次將三公升的容器裝滿 (3, 1)，(8)再倒入現有1公升水的五公升容器內，就這樣出現4公升的水 (0,4)。共需要8次，其步驟可以表示如下：(3, 0) – (0, 3) – (3, 3) –(1, 5) –(1, 0) –(0, 1) –(3, 1) –(0, 4)。

    範例 x=9, y=7, z=6，則可能的方法為 (9, 0) – (2, 7) – (2, 0) – (0, 2) – (9, 2) –(4, 7) –(4, 0) –(0, 4) –(9, 4) –(6, 7) 需10次。

    範例x=6, y=4, z=3，則可能的方法為 (6, 0)– ( 2, 4) – ( 2, 0) – (0, 2) – (6, 2) –(4, 4) –(4, 0) – (0, 4)– (6, 4) – (6, 0) 無法量出。

* 測資均為官方測資

* 為模擬正式競賽，WA 時 不公開正確答案!

* 加油~ !