ZeroJudge 解題筆記：c317. 硬幣問題！前傳

作者：王一哲
日期：2025年8月12日


ZeroJudge 題目連結：c317. 硬幣問題！前傳

解題想法

原則上盡量用面額最大的硬幣，這樣使用的硬幣總數會越少。

Python 程式碼

使用時間約為 31 ms，記憶體約為 3.3 MB，通過測試。

n = int(input())
for _ in range(n):
    x, a, b = map(int, input().split())
    na = x//a  # 硬幣 a 的數量
    x %= a  # x 剩下的數值
    nb = x//b  # 硬幣 b 的數量
    if x%b == 0:  # 如果硬幣 b 剛好可以整除 x
        print(na+nb)  # 找到答案，印出 na+nb
    else:  # 否則要測試將硬幣 a 換回來的狀況
        while na > 0:  # 如果還有硬幣 a
            na -= 1  # na 減 1
            x += a  # x 加 a
            if x%b == 0:  # 如果硬幣 b 剛好可以整除 x
                nb = x//b  # 找到硬幣 b 正確的數量
                break  # 中止 while 迴圈
        # 如果 x 可以被 b 整除印出 na+nb，否則印出 -1
        print(na+nb if x%b == 0 else "-1")

C++ 程式碼

使用時間約為 3 ms，記憶體約為 356 kB，通過測試。

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    for(int i=0; i<n; i++) {
        int x, a, b; cin >> x >> a >> b;
        int na = x/a;  // 硬幣 a 的數量
        x %= a;  // x 剩下的數值
        int nb = x/b;  // 硬幣 b 的數量
        if (x%b == 0) {  // 如果硬幣 b 剛好可以整除 x
            cout << na+nb << "\n";  // 找到答案，印出 na+nb
        } else {  // 否則要測試將硬幣 a 換回來的狀況
            while(na > 0) {  // 如果還有硬幣 a
                na--;  // na 減 1
                x += a;  // x 加 a
                if (x%b == 0) {  // 如果硬幣 b 剛好可以整除 x
                    nb = x/b;  // 找到硬幣 b 正確的數量
                    break;  // 中止 while 迴圈
                }
            }
            // 如果 x 可以被 b 整除印出 na+nb，否則印出 -1
            cout << (x%b == 0 ? na+nb : -1) << "\n";
        }
    }
    return 0;
}

使用時間約為 2 ms，記憶體約為 80 kB，通過測試。

#include <cstdio>
using namespace std;

int main() {
    int n; scanf("%d", &n);
    for(int i=0; i<n; i++) {
        int x, a, b; scanf("%d %d %d", &x, &a, &b);
        int na = x/a;  // 硬幣 a 的數量
        x %= a;  // x 剩下的數值
        int nb = x/b;  // 硬幣 b 的數量
        if (x%b == 0) {  // 如果硬幣 b 剛好可以整除 x
            printf("%d\n", na+nb);  // 找到答案，印出 na+nb
        } else {  // 否則要測試將硬幣 a 換回來的狀況
            while(na > 0) {  // 如果還有硬幣 a
                na--;  // na 減 1
                x += a;  // x 加 a
                if (x%b == 0) {  // 如果硬幣 b 剛好可以整除 x
                    nb = x/b;  // 找到硬幣 b 正確的數量
                    break;  // 中止 while 迴圈
                }
            }
            // 如果 x 可以被 b 整除印出 na+nb，否則印出 -1
            if (x%b == 0) printf("%d\n", na+nb);
            else puts("-1");
        }
    }
    return 0;
}