Algoogle

Algorithm for Programming Contest

AOJ 2007 Make Purse Light

Category: AOJ Tag: greedy

Make Purse Light

問題概要


解法


各硬貨の使わない枚数を数えるとシンプルにまとまる.
まず所持金のすべてを支払ったとして, 店員視点で渡すお釣りの硬貨の枚数の最小(最適な枚数)を考えるといい.
このとき, 返すそれぞれの硬貨の枚数は余計に渡した硬貨の枚数になるので,
意味のないやり取りを行なっていると考えられる.
だから答えは最初に持っていたそれぞれの硬貨の枚数からお釣りのそれぞれの硬貨の枚数をひいた数

コード


(2007.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>

using namespace std;

int main(){
    int a[4] = {10,50,100,500};
    int n;
    bool flag = true;
    while(cin >> n, n){
        int coin[4];
        int mcoin[4];

        cin >> coin[0] >> coin[1] >> coin[2] >> coin[3];

        n = coin[0] * 10 + coin[1] * 50 + coin[2] * 100 + coin[3] * 500 - n;
        for(int i = 3; i >= 0; i--){
            mcoin[i] = n / a[i];
            n -= mcoin[i] * a[i];
        }

        if(flag) flag = false;
        else cout << endl;
        for(int i = 0; i < 4; i++){
            if(coin[i] > mcoin[i]) cout << a[i] << ' ' << coin[i] - mcoin[i] << endl;
        }
    }
}

Comments