-
Notifications
You must be signed in to change notification settings - Fork 0
/
makingchange.cpp
71 lines (60 loc) · 1.47 KB
/
makingchange.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <cstring>
#include <map>
#include <sstream>
using namespace std;
#define F first
#define S second
typedef long long ll;
typedef pair<int,int> pii;
int m[6] = {1,2,4,10,20,40};
int num[6];
int change[3005];
int give[3005];
double n;
const int inf = 100000000;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
memset(change,0,sizeof(change));
for(int j=1;j<3001;j++){
int tmp = j;
int cnt = 0;
for(int i=5;i>=0;i--){
cnt += (tmp/m[i]);
tmp -= (m[i]*(tmp/m[i]));
if(tmp==0)
break;
}
change[j]=cnt;
}
while(cin>>num[0]>>num[1]>>num[2]>>num[3]>>num[4]>>num[5]>>n){
if(num[0]+num[1]+num[2]+num[3]+num[4]+num[5]==0)
break;
int x = (n+0.005)*100.0;
x/=5;
for(int i=0;i<3001;i++)
give[i] = inf;
give[0] = 0;
int tot = 0;
for(int i=0;i<6;i++){
tot += num[i]*m[i];
for(int j=1;j<=num[i];j++){
for(int k=tot;k>=m[i]*j;k--){
give[k] = min(give[k],give[k-m[i]*j]+j);
}
}
}
int ans = give[x];
for(int i=x+1;i<=100;i++)
ans = min(ans,give[i]+change[i-x]);
cout<<setw(3)<<ans<<'\n';
}
return 0;
}