1087: 零钱兑换

1087: 零钱兑换

时间限制: 1 Sec   内存限制: 128 MB

题目描述

小油瓶拿着100元去买糖吃，买了糖后要找零时，发现店里只剩下1元、2元和5元的纸币了。找回来一大堆零钱确实很烦人，所以小油瓶要求店员找给他的纸币的数量必须是最少的。 已知需要找还的钱的数额，同时店里有充足的1、2、5元纸币供找兑。编写一个程序，计算以最少数量的纸币凑出找零的数额时，各种纸币的使用数量。

输入

程序的输入为若干行，每行为一个整数，每个整数代表每次需找还的零钱的数量n（0<n<100），输入0则代表输入结束。

输出

根据每行输入的需找还的零钱的数量，程序计算相应的最小数量组合，并将纸币的使用数量以1元、2元、5元的顺序在相应行中输出，中间以一个空格相隔，每行输入对应一行输出。

样例输入 Copy

8

12

0

样例输出 Copy

1 1 1

0 1 2

提示

12元最好的组合为0张1元，1张2元，2张5元，所以对应的输出为0 1 2

#include<bits/stdc++.h>

using namespace std;

int main(){

int n;

while(1){

scanf("%d",&n);

if(n==0) break;

printf("%d %d %d\n",((n%5)%2),(n%5)/2,n/5);

}

return 0;

}