TopCoder

海之音
看著我,我是隻美麗的蝴蝶

User's AC Ratio

82.6% (185/224)

Submission's AC Ratio

25.6% (449/1753)

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

3
5 8 11
2

Sample Output 1

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

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1
1 3000 65536 262144 2
2 3000 65536 262144 3
3 3000 65536 262144 4
4 3000 65536 262144 5
5 3000 65536 262144 6
6 3000 65536 262144 7
7 3000 65536 262144 8
8 3000 65536 262144 9