# c317 - 硬幣問題 (前傳)

### 題目連結: [c317](https://zerojudge.tw/ShowProblem?problemid=c317)

### 題目解析
* X元的商品，只有兩種幣值 a, b，希望用最少的硬幣數量湊到
* 最少需要用到多少個硬幣?
* 硬幣是常見的程式問題，主要可以透過幣值兌換的方式取得最少的硬幣數量，另外湊硬幣也有不同的組合方式

### 題目類型
數學/排列組合/流程控制

### 範例測資解讀
* 輸入
* 為複合型輸入測資，第一行為整數 N 代表接下來有 N 筆輸入
* 第二行以後每一行有三個數字，分別代表 X, a, b
* 輸出
* 輸出每一行的 a, b 是否能湊出X元，若能湊出則輸出硬幣數量
* 不能湊出則輸出 -1

### 其他注意事項
* a, b 兩種幣值不會為零，且a幣值必定大於b幣值

### 程式解析
從提示中可以知道湊硬幣的方法
$144 = 11\cdot12 + 34 \Rightarrow 12+4=16$
$309 = 24\cdot11 + 9\cdot5 \Rightarrow 11+5=16$

因此程式的邏輯是：
* X元先使用 a幣值去除 (因為幣值較大，硬幣的使用數量較少)
* 若無法整除，則將 X/a 的最大數量(商數)-1，並且使用b幣值去除以a剩下的數量，再檢查是否整除
* 若仍無法整除，則 X/a 的最大數量(商數)再度 -1，並繼續使用b幣值去除以剩下的數量

若以 144 為例
step1: $144\div11 = 13 ... 1$
step2: $144-11\cdot(13-1) = 12$
step3: $12\div3 = 4 ... 0$
則幣值11的需要12個硬幣、幣值3的需要4個硬幣，總共需要16個硬幣

若以 309 為例
step1: $309\div24 = 12 ... 21$
step2: $309-24\cdot(12-1) = 45$
step3: $45\div9 = 5 ... 0$
則幣值24的需要11個硬幣、幣值9的需要5個硬幣，總共需要16個硬幣

因此我們可以將這個邏輯改寫成程式

numA = int(dollar/coinA)

while numA >=0:
    if (dollar-coinA*numA)%coinB !=0:
        numA -=1
    else:
        break

coinA: 為硬幣A的幣值
coinB: 為硬幣B的幣值

numA: 代表幣值a的數量
numB: 代表幣值b的數量

接著利用一個 while 迴圈調整 numA 的硬幣數量，湊出能整除的數量

以下為完整程式寫法

### 完整程式碼

import sys

# start
N = int(input())

for i in range(N):

    s = input()

    data = list(map(int, s.split()))

    dollar = data[0]
    coinA = data[1]
    coinB = data[2]

    #取得硬幣a一開始的數量
    numA = int(dollar/coinA)

    #利用一個 while 迴圈調整 numA的數量，直到能湊出整除為止
    while numA >=0:
        if (dollar-coinA*numA)%coinB !=0:
            numA -=1
        else:
            break
    
    if numA >=0:
        numB = int((dollar-coinA*numA)/coinB)
        total = numA+numB
        print(total)
    else:
        # 如果 while 迴圈不斷減少 numA 的數量直到 0 
        # 都還是湊不出來的話，代表 numB 也無法湊出答案
        print(-1)

###### tags: `基礎15題解` `APCS` `ZeroJudge`