C++|找零钱的有效方案数量

2022-06-22  本文已影响0人  ShowMeCoding

小明钱包里装着各种纸币。纸币有4种(纸币的类型有1元、3元、5元和10元),每一种分别有a、b、c、d张。现在小明要出门买东西,他需要支付N元,在不找零的情况下,请问能支付成功吗?如果能成功支付,那么请计算出有多少种支付方式;如果不能成功支付,就输出no。
输入描述:
输入共 1 行,包含 5个整数 a、b、c、d、n(其中,a、b、c、d分别表示1元、3元、5元和10元的数量),之间用一个空格隔开
a、b、c、d小于11
输出描述:
如果不能成功支付,则输出:no
如果可以成功支付,则输出:一个整数,表示支付方式的总数

示例 1:
输入:
1 1 1 1 1
输出:
1

#include <bits/stdc++.h>
using namespace std; 

int main() {
    // 请补全代码,实现题目功能
    int a, b, c, d, n, sum = 0, num = 0;
    cin >> a >> b >> c >> d >> n;
    for (int i = 0; i <= d; i++) {
        if (i*10 > n)
            break;
        for (int j = 0; j <= c; j++) {
            if ((i*10 + j*5) > n)
                break;
            for (int k = 0; k <= b; k++) {
                if ((i*10 + j*5 + k*3) > n)
                    break;
                for (int p = 0; p <= a; p++) {
                    sum = i*10 + j*5 + k*3 + p*1;
                    if (sum == n)
                        num += 1;
                    else if (sum > n)
                        break;
                }
            }
        }
    }
    // 有计算结果
    if (num) {
        cout << num << endl;
    }
    else {
        cout << "no" << endl;
    }
    return 0;
}
上一篇 下一篇

猜你喜欢

热点阅读