TopCoder

User's AC Ratio

90.9% (50/55)

Submission's AC Ratio

36.5% (127/348)

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

3
5 8 11
2

Sample Output

4

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

For Testdata: 0 ~ 0, Score: 11
For Testdata: 1 ~ 1, Score: 11
For Testdata: 2 ~ 2, Score: 11
For Testdata: 3 ~ 3, Score: 11
For Testdata: 4 ~ 4, Score: 11
For Testdata: 5 ~ 5, Score: 11
For Testdata: 6 ~ 6, Score: 11
For Testdata: 7 ~ 7, Score: 11
For Testdata: 8 ~ 8, Score: 12
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 3000 65536 65536
1 3000 65536 65536
2 3000 65536 65536
3 3000 65536 65536
4 3000 65536 65536
5 3000 65536 65536
6 3000 65536 65536
7 3000 65536 65536
8 3000 65536 65536