回分類題庫
h002: B.惱人的零錢
關鍵字: NPSC 2005 高中組初賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 47 Times / 39 Users | Submit : 282 Times / 56 Users | Accepted rate : 70%
題目加入時間 : 2011-11-10 10:22

Content: 简体中文

東東在買東西付帳,總是習慣直接從錢包中拿鈔票付帳,而懶得掏出零錢來。久而久之,錢包裡面累積了許多零錢,簡直重得不得了,所以東東終於受夠了!因此,她決定趁著今天買東西的時候,想辦法盡量減輕負擔。於是東東開始盤算要怎樣湊出足夠的零錢,才能讓付出去的硬幣個數越多越好。但是當她走到櫃台結帳時,才想到自己如果多付一些硬幣讓老闆找錢,說不定可以讓自己的錢包更輕!雖然老闆自己的零錢個數也不多,但是老闆人都很好,一定會用盡量少的硬幣找錢給東東。

因此,東東開始煩惱到底要怎麼給錢,才能夠盡量「用掉」最多的硬幣呢(所謂的「用掉」的硬幣個數,指的是拿出去的硬幣數,扣掉老闆找回來的硬幣數)?可惜的是,東東的算術一向不太靈光,因此希望你能幫忙他解決這個煩惱。

Input:

輸入資料的第一行是一個整數 n,代表共有 n 筆測試資料。接下來每筆測試資料有 3 行:第 1 行的數字 C 表示要買的東西的價格。第 2 行有 5 個數字 p1  p5  p10  p20  p50,分別是東東錢包裡面一元、五元、十元、二十元和五十元硬幣的個數。第 3 行有 5 個數字q1  q5  q10  q20  q50,是老闆所擁有的一元、五元、十元、二十元和五十元硬幣的個數。每筆測試資料的所有數字都在 0 到 10000 之間;同一行的數字之間會用一個空白隔開。你可以假設東東身上的錢足夠來購買該商品,而且至少有一種付錢的方法使得老闆可以找得開(如果需要找錢的話)。因為老闆和東東很不幸地很碰巧地一張鈔票都沒有,請不要問說為什麼不能換成大鈔。

Output:

你的輸出資料應該有 n 行,分別對應到 n 筆輸入的測試資料。每一行要輸出一個數字表示東東付完帳之後,剩餘的硬幣總數。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
2
25
10 3 2 1 3
0 0 0 0 0
25
0 3 2 2 3
1 1 1 1 1

Sample Output :

6
4

Hint :

Author :

NPSC 2005 高中組初賽 (管理員:sagit)

  Solve it!   Status Forum