解析的な解法

新年明けましておめでとうございます。

　今日は新年早々AOJで問題を解きました。
　その問題の解法について解説を読んでみる勉強になったことがあったので、メモしておこうと思います。
　まず、この問題（ここから）は、解説によると全検索でも求められるそうですが、４つの硬貨を用いる問題なのでループの数が面倒になります。そこで、よく自販機なので用いる両替テクニックを実際に考えてみることにしてみます。まず、考えることはちょうど硬貨が支払えるかと言うことを考えるはずです。この時に財布で起こってることは各硬貨について枚数が足りているかを考えます。枚数が足りないときは、代金より多いお金を支払い、おつりを貰います。また、１００円のものを買うとき財布に１０円玉が２０枚あるとします。この時の支払いは１０円を２０枚支払い、１枚の１００円硬貨をおつりとしてもらうことが硬貨の枚数削減の最良の手法になります。

　この考えを式に直します。
　　例として次のような場合を考えます。
　　　
　　支払額　＝＞　５３０
　　１０円　＝＞　１枚、５０　＝＞　１３枚、１００円　＝＞　７枚、５００円　＝＞　１６枚

　　支払い後の残金は８８２０円になります。この代金について硬貨の枚数を一番少なくしてみます。
　　８８２０　÷　５００　＝　１６・・・３２０
　　　３２０　÷　１００　＝　３　・・・　２０
　　　　２０　÷　　５０　＝　０　・・・　２０
　　　　２０　÷　　１０　＝　２　・・・　　０

　　この各硬貨の枚数について、元々所持していた枚数と差をとります。
　　１６　ー　１６　＝　　０
　　　７　ー　　３　＝　　４
　　１３　ー　　０　＝　１３
　　　１　ー　　２　＝　−１

　　この解は各貨幣について
　　　　　　　　解　＞　０　・・・　財布から支払った貨幣の枚数
　　　　　　　　解　＝　０　・・・　財布の中の貨幣の枚数が変化していない
　　　　　　　　解　＜　０　・・・　おつりとして増えた貨幣の枚数

　　つまり、この問題は上の作業で得られた解の０より大きい枚数について回答します。

　この考えをコードにしたものです。

#include <iostream>
using namespace std;

int main()
{
  int P, price[4][2] = {{10,}, {50,}, {100,}, {500,}};
  bool flag = false;
  while (cin >> P && P) {
    int total = 0;
    for (int i = 0; i < 4; i++) {
      cin >> price[i][1];
      total += (price[i][0] * price[i][1]);
    }
    P -= total;
    P = -P;
    for (int i = 3; i >= 0; i--) {
      price[i][1] = price[i][1] - P / price[i][0]; 
      P = P % price[i][0];
    }
    if (flag) cout << endl;
    for (int i = 0; i < 4; i++) {
      if (price[i][1] > 0) cout << price[i][0] << " " << price[i][1] << endl;
    }
    flag = true;
  }

  return 0;
}