#P3085. Quick Change

Quick Change

题目描述

J.P.FlatheadJ.P. Flathead经营的杂货店雇佣廉价劳动力(通常是高中生)负责收银台工作。这些员工在给顾客找零时经常出错。FlatheadFlathead发现,由于这些错误,他损失的金额甚至可能超过利润——因为员工往往会多找零钱给顾客。

FlatheadFlathead希望你编写一个程序,计算应该找给顾客的硬币数量,包括:0.250.25美元硬币(2525美分),0.100.10美元硬币(1010美分),0.050.05美元硬币(55美分),0.010.01美元硬币(11美分)。当找零金额不超过5.005.00美元时,必须全部用硬币支付。需要确保给出的硬币总数最少。例如,1.241.24美元的找零应兑换为:442525美分、221010美分、0055美分和4411美分。

输入格式

第一行输入整数NN1N1001 \leq N \leq 100),表示测试数据集的数量
每个测试数据包含一个整数CC1C5001 \leq C \leq 500),表示需要找零的金额(单位:美分)

输出要求

对每个测试数据,输出以下内容:

数据集编号 Q QUARTER(S), D DIME(S), n NICKEL(S), P PENNY(S)

其中:QQ0.250.25美元硬币数量 ,DD0.100.10美元硬币数量 , nn0.050.05美元硬币数量 ,PP0.010.01美元硬币数量 。

输入样例

3
124
25
194

输出样例

1 4 QUARTER(S), 2 DIME(S), 0 NICKEL(S), 4 PENNY(S)
2 1 QUARTER(S), 0 DIME(S), 0 NICKEL(S), 0 PENNY(S)
3 7 QUARTER(S), 1 DIME(S), 1 NICKEL(S), 4 PENNY(S)

题目来源

2006年大纽约地区程序设计竞赛