【問題A05】旅行支票之兌換                     [回前頁]

對經常出國的人來說，金錢的攜帶是免不了的困擾。為避免遺失與冒用，我們可選擇購買國際知名的銀行所提供的旅行支票，預先在這些支票上簽名，等後來到達目的地購買商品時，再簽一次名，並寫上收受者的名字，就可達到如現金般的便利。又因為沒有相同的簽名，其他人就無法兌現該支票，故若不巧支票遺失，我們可儘快聯絡該銀行，來獲得等面額的補償，增加多一層保障。然而，旅行支票的面額大小不一，同樣的總額會有幾種不同的組合方式，譬如，總額為一千兩百元能以五百元的支票兩張及兩百元的支票一張，或兩百元的支票六張等方式組成。在銀行可充分供應各式組合的情形下，假設我們為了攜帶方便，希望支票的總張數最少，面對此需求，請設計一個程式來便利即將出國者，以解決此旅行支票之兌換問題。

輸入說明：

第一行為自然數，表示旅行支票有幾種不同面額之選擇N (0<N≦30)。

第二行至第N+1行為自然數，分別代表旅行支票的面額值，每一行代表一面額值，這些數值皆不相同，但不一定由小到大排列。

第N+2行為自然數，代表兌換的總額S。

輸出說明：

第一行為整數M，指明有幾種總張數最少之最佳解，其中，M=0表示這些不同面額旅行支票無法組合出兌換的總額；而M>0代表共有M種最佳解，兌換的明細另由後續幾行表列出，如下所示。

第二行為自然數，代表兌換的總張數。

第三行至第M+2行各為N個非負整數，以空白隔開，分別對應該面額值的旅行支票之張數。

【範例一】

輸入格式：

2

100

20

110

輸出格式：

0

【範例二】

輸入格式：

3

500

200

1000

1200

輸出格式：

1

2

0 1 1

【範例三】

輸入格式：

4

500

1200

1000

100

2100

輸出格式：

1

3

0 0 2 1

【範例四】

輸入格式：

3

10

50

30

60

輸出格式：

2

2

1 1 0

0 0 2