769 . 量杯問題

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

smgshabc123

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

100.0% (5/5)

Tags

apcsc apcsc-graph

Description

有 N 個無刻度量杯分別有容量 A1,A2,…,AN，你能做的操作有：

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

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

Input Format

輸入第一行是一個正整數 N 代表量杯數，1≤N≤4。
第二行有 N 個空白分隔的正整數 A1,A2,…,AN 表示量杯容量，1≤Ai≤50。
第三行有一個正整數 T 表示目標容量，1≤T≤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