769 . 量杯問題

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

smgshabc123

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

100.0% (2/2)

Tags

apcsc apcsc-graph

Description

有 $N$ 個無刻度量杯分別有容量 $A_1, A_2, \dots, A_N$，你能做的操作有：

  • 把某個量杯加滿水
  • 把某個量杯倒空
  • 把某量杯的水全部倒入另一量杯中，如果沒滿出來則倒光為止
  • 把某量杯的水全部倒入另一量杯中，如果滿出來則倒滿為止

請問你至少要做幾次操作才能量出 $T$ 公升的水在某個量杯中。

Input Format

輸入第一行是一個正整數 $N$ 代表量杯數，$1\le N\le 4$。
第二行有 $N$ 個空白分隔的正整數 $A_1, A_2, \dots, A_N$ 表示量杯容量，$1\le A_i\le 50$。
第三行有一個正整數 $T$ 表示目標容量，$1\le T\le 50$。

Output Format

輸出一行一個整數代表最少操作次數，如果做不到請輸出 $-1$。

Sample Input 1

2
5 3
1

Sample Output 1

4

Hints

Problem Source

TIOJ

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~20 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2
16 1000 524288 65536 2
17 1000 524288 65536 2
18 1000 524288 65536 2
19 1000 524288 65536 2
20 1000 524288 65536 2
Submit
Back to Top