Make Purse Light - kyoupuro @ ウィキ

2007 : Make Purse Light

問題文

解説

お釣りの硬貨の枚数を最小にするためには、どの硬貨を何枚渡せばいいかを出力する問題。
持っているお金を全て店員に渡せば、最適な枚数が返ってくる。
つまり、お金を全て渡して「持っているお金の枚数-戻ってきたお金の枚数」を計算すればいい。
参考→Make Purse Light 解説

あと、1つのデータセット毎に改行する必要があるので注意。

プログラム

C

C++

#include <iostream>
using namespace std;

const int yen[4] = {10, 50, 100, 500};

int main() {
   int n;
   bool first = true;
   while (cin >> n, n) {
       if (first) first = false;
       else cout << endl;

       int c[4];
       int total = 0;
       for (int i = 0; i < 4; i++) {
           cin >> c[i];
           total += yen[i] * c[i];
       }

       total -= n;
       for (int i = 3; i >= 0; i--) {
           if (total >= yen[i]) {
               c[i] -= total/yen[i];
               total = total%yen[i];
           }
       }

       for (int i = 0; i < 4; i++) {
           if (c[i] > 0) {
               cout << yen[i] << ' ' << c[i] << endl;
           }
       }
   }

   return 0;
}

Java