POJ 3085 Quick Change (贪心)

Quick Change

Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 5801   Accepted: 4175

Description

J.P. Flathead’s Grocery Store hires cheap labor to man the checkout stations. The people he hires (usually high school kids) often make mistakes making change for the customers. Flathead, who’s a bit of a tightwad, figures he loses more money from these
mistakes than he makes; that is, the employees tend to give more change to the customers than they should get.

Flathead wants you to write a program that calculates the number of quarters ($0.25), dimes ($0.10), nickels ($0.05) and pennies ($0.01) that the customer should get back. Flathead always wants to give the customer’s change in coins if the amount due back
is $5.00 or under. He also wants to give the customers back the smallest total number of coins. For example, if the change due back is $1.24, the customer should receive 4 quarters, 2 dimes, 0 nickels, and 4 pennies.

Input

The first line of input contains an integer which is the number of datasets that follow. Each dataset consists of a single line containing a single integer which is the change due in cents, C, (1 ≤ C 
500).

Output

For each dataset, print out the dataset number, a space, and the string:

Q QUARTER(S), D DIME(S), n NICKEL(S), P PENNY(S)

Where Q is he number of quarters, D is the number of dimes, n is the number of nickels and P is the number of pennies.

Sample Input

3
124
25
194

Sample Output

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)

Source

Greater New York 2006

就是找零钱,无需多言。

代码:

#include <iostream>

#include <algorithm>

#include <stdio.h>

using namespace std;

int main()

{

int n,m,i;

int f[4]={25,10,5,1};

while(scanf("%d",&n)!=EOF&&n)

{

for( i=1;i<=n;i++)

{

int k[4]={0};

scanf("%d",&m);

while(m>=f[0]) {m-=f[0];k[0]++;}

while(m>=f[1]) {m-=f[1];k[1]++;}

while(m>=f[2]) {m-=f[2];k[2]++;}

while(m>=f[3]) {m-=f[3];k[3]++;}

printf("%d %d QUARTER(S), %d DIME(S), %d NICKEL(S), %d PENNY(S)\n",i,k[0],k[1],k[2],k[3]);

}

}

return 0;

}

POJ 3085 Quick Change (贪心),布布扣,bubuko.com

时间: 08-15

POJ 3085 Quick Change (贪心)的相关文章

POJ 3085 -- Quick Change

Quick Change Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 6288   Accepted: 4468 Description J.P. Flathead’s Grocery Store hires cheap labor to man the checkout stations. The people he hires (usually high school kids) often make mistak

poj 2431 Expedition (贪心+优先队列)

Expedition Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 6890   Accepted: 2065 Description A group of cows grabbed a truck and ventured on an expedition deep into the jungle. Being rather poor drivers, the cows unfortunately managed to

POJ 1659 Frogs&#39; Neighborhood (贪心)

题意:中文题. 析:贪心策略,先让邻居多的选,选的时候也尽量选邻居多的. 代码如下: #pragma comment(linker, "/STACK:1024000000,1024000000") #include <cstdio> #include <string> #include <cstdlib> #include <cmath> #include <iostream> #include <cstring>

POJ 1328 Radar Installation 贪心题解

本题是贪心法题解,不过需要自己观察出规律,这就不容易了,很容易出错. 一般网上做法是找区间的方法. 这里给出一个独特的方法: 1 按照x轴大小排序 2 从最左边的点循环,首先找到最小x轴的圆 3 以这个圆判断可以包括右边的多少个圆,直到不可以包括下一个点,那么继续第2步,画一个新圆. 看代码吧,应该很清晰直观的了. 效率是O(n),虽然有嵌套循环,但是下标没有重复,一遍循环就可以了,故此是O(n). #include <stdio.h> #include <cmath> #incl

POJ Charlie&#39;s Change 查理之转换(多重背包,微变形)

题意:给定身上的4种硬币,分别是1 ,5 ,10, 25面额各有多张,要求组成面额p的硬币尽可能多.输出组成p的4种硬币各自的数量. 思路:多重背包,300+ms.用01背包+二进制的方法.记录下所有的硬币的个数以及4种硬币分别的个数,注意初始化dp数组的不同之处. 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #define LL long long 5 using namespace

POJ 3190 Stall Reservations(贪心+优先队列优化)

Description Oh those picky N (1 <= N <= 50,000) cows! They are so picky that each one will only be milked over some precise time interval A..B (1 <= A <= B <= 1,000,000), which includes both times A and B. Obviously, FJ must create a reserv

Poj 1328 Radar Installation 贪心

题目链接:http://poj.org/problem?id=1328 Radar Installation Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 52768   Accepted: 11867 Description Assume the coasting is an infinite straight line. Land is in one side of coasting, sea in the othe

POJ 3190 Stall Reservations贪心

POJ 3190 Stall Reservations贪心 Description Oh those picky N (1 <= N <= 50,000) cows! They are so picky that each one will only be milked over some precise time interval A..B (1 <= A <= B <= 1,000,000), which includes both times A and B. Obvi

[ACM] POJ 1328 Radar Installation (贪心,区间选点问题)

Radar Installation Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 51131   Accepted: 11481 Description Assume the coasting is an infinite straight line. Land is in one side of coasting, sea in the other. Each small island is a point loca