Problem #1042 - ECNU Online Judge

单点时限: 1.0 sec

内存限制: 256 MB

超市的自动柜员机 (POS) 要找给顾客各种数值的现金，表面上看，这是一个很简单的任务，但交给机器办就不简单了。你作为一个计算机专家，要求写一个程序来对付这个「简单」的问题。

你的自动柜员机有以下的币种： $100$ 元、 $50$ 元、 $20$ 元、 $10$ 元、 $5$ 元、 $2$ 元、 $1$ 元。你可以假设每种钱币的数量是无限的。现在有一笔交易，需要找给客户 $m$ 元，请你设计一个算法，使得找给顾客的钱币张数最少。

第一行仅有一个整数 $n$ ( $1 \leq n \leq 10000$ ), 表示有几组测试数据。

每组测试数据仅有一行，每行只有一个整数 $m$ ( $0 < m < 2 \cdot 10^{9}$ )，表示需要找的钱币数。

每组测试数据输出一行，每行有 $7$ 个整数 (两两之间有一个空格，结尾不能有空格)，表示 $100$ 元、 $50$ 元、 $20$ 元、 $10$ 元、 $5$ 元、 $2$ 元、 $1$ 元所需要的张数。

Input

2
16
200

Output

0 0 0 1 1 0 1
2 0 0 0 0 0 0

991 人解决，1132 人已尝试。

1231 份提交通过，共有 2309 份提交。

0.6 EMB 奖励。

创建: 19 年，1 月前.

修改: 7 年，3 月前.

最后提交: 3 周前.

来源: N/A

binary search greedy

1042. 付款问题