1008 . 量杯問題
TopCoder
Tags
Description
這裡有各種不同容量的量杯可以裝水，可是有時候所有量杯的容量都不是剛好我們想要的，因此我們要用些技巧來量出我們所需要的水量。
舉例來說，這裡有一個 3 公升和一個 5 公升的量杯，如果我們想量出 4 公升的水，最快的方法是
(1)將 5 公升量杯裝滿
(2)將 5 公升量杯內的水倒入 3 公升量杯倒滿為止
(3)將 3 公升量杯內的水倒掉
(4)將 5 公升量杯內的水倒入 3 公升量杯倒光為止
(5)將 5 公升量杯裝滿
(6)將 5 公升量杯內的水倒入 3 公升量杯倒滿為止
如此一來，5公升量杯內剩下4公升的水，就是我們想要的水量了，而我們總共用了 6 個動作來達成目標。現在請寫一個程式，給定量杯數量和每一個量杯的容量，請算出最少需要幾個動作來達成目標，或是不可能做到。注意：所要的水必須只裝在一個量杯內，不能由多個量杯的水量總合來達成目標，另外所有量杯一開始都是空的。
Input Format
每次輸入三行，第一行有一個數字 $n$，代表量杯數量，其中 $1\le n\le 5$，第二行有 $n$ 個數字 $m_1, m_2, \dots, m_n$，皆以一個空白分隔，分別代表每一個量杯的容量，其中 $1\le m_i \le 50$，第三行有一個數字 $t$，代表要量出的水量，其中 $1\le t \le 50$。
Output Format
對於每一筆輸入，請輸出一個正整數，代表達成目標所需的步驟數，或是輸出 -1，代表不可能做到。
Sample Input 1
5 8 11
2
Sample Output 1
Hints
範例輸出說明
(a)將一個量杯裝滿水
(b)將一個量杯內的水倒光
(c)將一個量杯內的水倒到另一個量杯內，倒滿或是倒光為止
以上三項分別算一個動作，以範例來說，最快是 4個動作。
步驟一 把 5 公升量杯裝滿 (5/5, 0/8, 0/11)
步驟二 把 5 公升量杯內的水倒到 11 公升量杯內 (0/5, 0/8, 5/11)
步驟三 把 8 公升量杯裝滿 (0/5, 8/8, 5/11)
步驟四 把 8 公升量杯內的水倒到 11 公升量杯內 (0/5, 2/8, 11/11)
Problem Source
原TIOJ1008 / 建國中學95學年度校內資訊能力競賽(5, cup)
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 11 |
| 2 | 1 | 11 |
| 3 | 2 | 11 |
| 4 | 3 | 11 |
| 5 | 4 | 11 |
| 6 | 5 | 11 |
| 7 | 6 | 11 |
| 8 | 7 | 11 |
| 9 | 8 | 12 |