#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
int num[6],sum[6];
int mi(int num[],int a[],int count1)
{
int sum=0;
for(int i=5;i>1;i--)
{
if(count1>a[i]*num[i])
{
sum=sum+num[i];
count1=count1-a[i]*num[i];
}
else
{
int temp=count1/a[i];
sum=sum+temp;
count1=count1-temp*a[i];
}
}
if(count1>num[1])
return -1;
else
return sum+count1;
}
int ma(int sum[],int num[],int a[],int count1)
{
int sum1=0;
for(int i=5;i>1;i--)
{
if(count1>sum[i-1])
{
int t=(count1-sum[i-1])/a[i];
if((count1-sum[i-1])%a[i]>0)
t++;
sum1=sum1+t;
count1=count1-t*a[i];
}
}
if(count1>num[1])
return -1;
else
return sum1+count1;
}
void pd(int sum[],int num[],int a[],int count1)
{
int tmin=mi(num,a,count1);
if(tmin==-1)
printf("-1 -1
");
else
{
int tmax=ma(sum,num,a,count1);
if(tmax==-1)
printf("-1 -1
");
else
printf("%d %d
",tmin,tmax);
}
}
int main()
{
int t;
int a[6]={0,1,5,10,50,100};
scanf("%d",&t);
while(t--)
{
int count1;
scanf("%d",&count1);
for(int i=1;i<=5;i++)
{
scanf("%d",&num[i]);
}
for(int i=1;i<=5;i++)
sum[i]=sum[i-1]+a[i]*num[i];
if(sum[5]<count1)
printf("-1 -1
");
else
pd(sum,num,a,count1);
}
return 0;
}
coins
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1100 Accepted Submission(s): 316
Problem Description
"Yakexi, this is the best age!" Dong MW works hard and get high pay, he has many 1 Jiao and 5 Jiao banknotes(纸币), some day he went to a bank and changes part of his money into 1 Yuan, 5 Yuan, 10 Yuan.(1 Yuan = 10 Jiao)
"Thanks to the best age, I can buy many things!" Now Dong MW has a book to buy, it costs P Jiao. He wonders how many banknotes at least,and how many banknotes at most he can use to buy this nice book. Dong MW is a bit strange, he doesn't like to get the change, that is, he will give the bookseller exactly P Jiao.
"Thanks to the best age, I can buy many things!" Now Dong MW has a book to buy, it costs P Jiao. He wonders how many banknotes at least,and how many banknotes at most he can use to buy this nice book. Dong MW is a bit strange, he doesn't like to get the change, that is, he will give the bookseller exactly P Jiao.
Input
T(T<=100) in the first line, indicating the case number.
T lines with 6 integers each:
P a1 a5 a10 a50 a100
ai means number of i-Jiao banknotes.
All integers are smaller than 1000000.
T lines with 6 integers each:
P a1 a5 a10 a50 a100
ai means number of i-Jiao banknotes.
All integers are smaller than 1000000.
Output
Two integers A,B for each case, A is the fewest number of banknotes to buy the book exactly, and B is the largest number to buy exactly.If Dong MW can't buy the book with no change, output "-1 -1".
Sample Input
3 33 6 6 6 6 6 10 10 10 10 10 10 11 0 1 20 20 20
Sample Output
6 9 1 10 -1 -1
Author
madfrog
代码