16. 量杯問題

0 Judge

Code: 0


量杯問題

sprout

題目敘述

實驗室有很多量杯,但取用時不一定有符合需求的容量,因此我們可以使用一種技巧來得到需要的量。比如說現在有一個三公升的量杯與五公升的量杯,要取出四公升的量的話,我們可以這樣做:

  1. 把五公升的量杯裝滿水
  2. 把五公升量杯裡的水倒滿三公升的量杯
  3. 把三公升裡剩下的水倒掉
  4. 把五公升量杯剩下的水全部倒到三公升量杯
  5. 把五公升的量杯裝滿水
  6. 把五公升量杯裡的水倒滿三公升的量杯

此時五公升的量杯裡就恰好剩下四公升的水了。

如果給你任意的空量杯,你能算出最少要幾個步驟才能得到需要的量嗎?

一個步驟可以做下列事情

  • 把一個量杯裝滿水
  • 把一個量杯內的水倒掉
  • 把一個量杯的水全部倒給或是倒滿另一個量杯

輸入說明

每筆測資點只有一筆測資,佔三行。第一行有一個整數$T$,表示有幾個量杯,第二行有$T$個整數,分別表示每個量杯的容量為何。最後一行有一個整數$Q$,為詢問的容量。

保證

  • $1\leq T\leq 5$
  • $1\leq 量杯容量\leq 50$
  • $1\leq Q\leq 50$

    輸出說明

輸出一行,為最少步數。若無法完成輸出$-1$。

範例輸入

3
5 8 11
2

範例輸出

4

提示

來源

TIOJ 1008


Judge Setting

run-time limit: 300 ms
memory limit: 655360 byte
測資數量: 0