Page 7 of 16
Posted: Mon Feb 14, 2005 11:55 pm
You don't need to calculate the result every time. Just calculate once and store them in a global array.

Regards
Sanny

Posted: Tue Feb 15, 2005 10:21 am
Thanky you for your advice but I'm getting now WA and I'm really confused( I beyed all the output rules )

Code: Select all

``````#include <cstdio>
#include <cstring>
using namespace std;

const int M = 11, MAX_N = 300 * 100;
int coins[] = { 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000 };
long long dp[MAX_N+1] = { 0 };

void solve( int N )
{
dp[0] = 1;

for( int j = 0; j < M; ++j )
for( int i = 1; i <= N; ++i )
if( i >= coins[j] )
dp[i] += dp[i - coins[j]];
}

int main()
{
double d;

solve( MAX_N );

scanf( "%lf", &d );
while( 	d != 0.0 )
{
char num1[6], num2[100];
sprintf( num1, "%.2lf", d );
sprintf( num2, "%lld", dp[(int)(d * 100)] );

int k1 = 6 - strlen( num1 );
int k2 = 17 - strlen( num2 );

for( int i = 0; i < k1; ++i ) printf( " " ); printf( "%.2lf", d );
for( int i = 0; i < k2; ++i ) printf( " " ); printf( "%lld\n", dp[(int)(d*100)] );

scanf( "%lf", &d );
}
return 0;
}
``````

### 147 Dollars WA(I can't figure it out!!!)

Posted: Tue Feb 15, 2005 7:14 pm
I just don't see it, is my algorihtm wrong or what?

Code: Select all

``````#include <cstdio>
#include <cstring>
using namespace std;

const int M = 11, MAX_N = 300 * 100;
long long coins[] = { 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000 };
long long dp[MAX_N+1] = { 0 };

void solve()
{
dp[0] = 1;

for( int j = 0; j < M; ++j )
for( int i = coins[j]; i <= MAX_N; ++i )
dp[i] += dp[i - coins[j]];
}

int main()
{
float d;

solve();

scanf( "%f", &d );
while( 	d != 0.0 )
{

int d2 = (int)(d * 100.0 + 0.001); //'cause of the rounding problem

char num1[6], num2[100];
sprintf( num1, "%.2f", d );
sprintf( num2, "%lld", dp[d2] );

int k1 = 6 - strlen( num1 );
int k2 = 17 - strlen( num2 );

for( int i = 0; i < k1; ++i ) printf( " " ); printf( "%.2f", d );
for( int i = 0; i < k2; ++i ) printf( " " ); printf( "%lld\n", dp[d2] );

scanf( "%f", &d );
}

return 0;
}
``````

Posted: Tue Feb 15, 2005 7:29 pm
Never mind this post I sollved the problem

### 147 bug

Posted: Mon Feb 28, 2005 5:24 pm

Code: Select all

``````
/*
My input
1===>target=100
2===>target=200
3
4
5
6
7
8
9
10

output
50
293
973
2729
6100
12319
22572
38836
63142
104512

right ans
1.00                50
2.00               293
3.00              1022
4.00              2728
5.00              6149
6.00             12368
50.00         513269191
*/

#include <iostream>
#include <string>
using namespace std;
#define N 11
#define OUTPUT 1

int change(const int value[N],int coin_mount[N],
int ori_mount[N],const int &target,
int &way,int where)
{
int i,gether=0,howmany=0
,left=target;
bool flag=false;

for(i=where;i<N;i++)
{
if(value[i]<=left)
{
if(flag==false)
{
where=i;
flag=true;
}

coin_mount[i]=left/value[i];
left=target%value[i];
}
else
{
coin_mount[i]=0;
}
}
way++;
#ifdef OUTPUT
int aamount=0;
for(i=0;i<N;i++)
{
if(coin_mount[i])
{
aamount+=coin_mount[i]*value[i];
}
cout<<coin_mount[i]<<",";
}
cout<<"nt="<<aamount<<" way= "<<way<<endl;
if(way%200==0)
{
cout<<"press 'enter' to continue"<<endl;
cin.get();
}
#endif
if(where==N-1)
{
return way;
}

while(coin_mount[where]>0)
{
//if(coin_mount[where]==0)
//{
//change(value,coin_mount,ori_mount,target,++way,where+1);
//}
if(//coin_mount[where]==2 &&
coin_mount[where+1]==1
//&& coin_mount[where+2]==0
&& where==8
)
{//bug  for way x,x,x,x,x,x,x,2 0 2
way++;
#ifdef OUTPUT
cout<<"x,x,x,x,x,x,x,x,x,0,y bug  for way~~~~~~~ "<<endl;
#endif
}

coin_mount[where]--;
int target1=value[where];
for(i=where+1;i<11;i++)
{//count target
target1+=coin_mount[i]*value[i];
}
change(value,coin_mount,ori_mount,target1,way,where+1);
}
#ifdef OUTPUT
while(coin_mount[where]==0 || where<N)
{//i dun konw if this segment of code is usable
cout<<"!!!!!where="<<where<<endl;
where++;
}
#endif
return way;

}

int Dollars(const int value[N],int coin_mount[N],
const int &target,
int way,int counter)
{
int i,gether=0,howmany=0
,left=target,where,ori_mount[N]={0};
bool flag=false;
for(i=0;i<N;i++)
{//find the first
if(value[i]<=left)
{
if(flag==false)
{
where=i;
flag=true;
}
coin_mount[i]=left/value[i];
ori_mount[i]=coin_mount[i];
left=target%value[i];
}
else
{
coin_mount[i]=0;
}
}
#ifdef OUTPUT
for(i=0;i<N;i++)
{
cout<<coin_mount[i]<<",";
}
cout<<endl;
int amount=coin_mount[where];
#endif
way=0;
while(coin_mount[where]>0)
{
coin_mount[where]--;

if(coin_mount[where]==0)
{
change(value,coin_mount,ori_mount,target,++way,where+1);
}
else
{
int target1=value[where];
for(i=where+1;i<11;i++)
{
if(coin_mount[i])
{
target1+=coin_mount[i]*value[i];
}
}
change(value,coin_mount,ori_mount,target1,++way,where+1);
}
}

return way;
}

int main()
{
int value[N]={10000, 5000, 2000, 1000, 500,200
, 100, 50, 20, 10 ,5};
int target=300;
//target*=100;
//set target as input~~
int coin_mount[N]={0};

if(target==0) cout<<"1";
//for(target=100;target<1001;target+=100){
int ans=Dollars(value,coin_mount,target,0,0);
cout<<ans<<endl;
//}

return 0;
}

``````

Code: Select all

``````0,0,0,0,0,1,1,0,0,0,0,
0,0,0,0,0,0,3,0,0,0,0,nt=300 way= 2
0,0,0,0,0,0,2,2,0,0,0,nt=300 way= 3
0,0,0,0,0,0,2,1,2,1,0,nt=300 way= 4
x,x,x,x,x,x,x,x,x,0,y bug  for way~~~~~~~
0,0,0,0,0,0,2,1,1,3,0,nt=300 way= 6
0,0,0,0,0,0,2,1,1,2,2,nt=300 way= 7
0,0,0,0,0,0,2,1,1,1,4,nt=300 way= 8
0,0,0,0,0,0,2,1,1,0,6,nt=300 way= 9
!!!!!where=9
!!!!!where=10
0,0,0,0,0,0,2,1,0,5,0,nt=300 way= 10
0,0,0,0,0,0,2,1,0,4,2,nt=300 way= 11
0,0,0,0,0,0,2,1,0,3,4,nt=300 way= 12
0,0,0,0,0,0,2,1,0,2,6,nt=300 way= 13
0,0,0,0,0,0,2,1,0,1,8,nt=300 way= 14
0,0,0,0,0,0,2,1,0,0,10,nt=300 way= 15
!!!!!where=9
!!!!!where=10
!!!!!where=8
!!!!!where=9
!!!!!where=10
0,0,0,0,0,0,2,0,5,0,0,nt=300 way= 16
0,0,0,0,0,0,2,0,4,2,0,nt=300 way= 17
0,0,0,0,0,0,2,0,4,1,2,nt=300 way= 18
0,0,0,0,0,0,2,0,4,0,4,nt=300 way= 19
!!!!!where=9
!!!!!where=10
0,0,0,0,0,0,2,0,3,4,0,nt=300 way= 20
0,0,0,0,0,0,2,0,3,3,2,nt=300 way= 21
0,0,0,0,0,0,2,0,3,2,4,nt=300 way= 22
0,0,0,0,0,0,2,0,3,1,6,nt=300 way= 23
0,0,0,0,0,0,2,0,3,0,8,nt=300 way= 24
!!!!!where=9
!!!!!where=10
0,0,0,0,0,0,2,0,2,6,0,nt=300 way= 25
0,0,0,0,0,0,2,0,2,5,2,nt=300 way= 26
0,0,0,0,0,0,2,0,2,4,4,nt=300 way= 27
0,0,0,0,0,0,2,0,2,3,6,nt=300 way= 28
0,0,0,0,0,0,2,0,2,2,8,nt=300 way= 29
0,0,0,0,0,0,2,0,2,1,10,nt=300 way= 30
0,0,0,0,0,0,2,0,2,0,12,nt=300 way= 31
!!!!!where=9
!!!!!where=10
0,0,0,0,0,0,2,0,1,8,0,nt=300 way= 32
0,0,0,0,0,0,2,0,1,7,2,nt=300 way= 33
0,0,0,0,0,0,2,0,1,6,4,nt=300 way= 34
0,0,0,0,0,0,2,0,1,5,6,nt=300 way= 35
0,0,0,0,0,0,2,0,1,4,8,nt=300 way= 36
0,0,0,0,0,0,2,0,1,3,10,nt=300 way= 37
0,0,0,0,0,0,2,0,1,2,12,nt=300 way= 38
0,0,0,0,0,0,2,0,1,1,14,nt=300 way= 39
0,0,0,0,0,0,2,0,1,0,16,nt=300 way= 40
!!!!!where=9
!!!!!where=10
0,0,0,0,0,0,2,0,0,10,0,nt=300 way= 41
0,0,0,0,0,0,2,0,0,9,2,nt=300 way= 42
0,0,0,0,0,0,2,0,0,8,4,nt=300 way= 43
0,0,0,0,0,0,2,0,0,7,6,nt=300 way= 44
0,0,0,0,0,0,2,0,0,6,8,nt=300 way= 45
0,0,0,0,0,0,2,0,0,5,10,nt=300 way= 46
0,0,0,0,0,0,2,0,0,4,12,nt=300 way= 47
0,0,0,0,0,0,2,0,0,3,14,nt=300 way= 48
0,0,0,0,0,0,2,0,0,2,16,nt=300 way= 49
0,0,0,0,0,0,2,0,0,1,18,nt=300 way= 50
0,0,0,0,0,0,2,0,0,0,20,nt=300 way= 51
!!!!!where=9
!!!!!where=10
!!!!!where=8
!!!!!where=9
!!!!!where=10
!!!!!where=7
!!!!!where=8
!!!!!where=9
!!!!!where=10
0,0,0,0,0,0,1,4,0,0,0,nt=300 way= 52
0,0,0,0,0,0,1,3,2,1,0,nt=300 way= 53
x,x,x,x,x,x,x,x,x,0,y bug  for way~~~~~~~
0,0,0,0,0,0,1,3,1,3,0,nt=300 way= 55
0,0,0,0,0,0,1,3,1,2,2,nt=300 way= 56
0,0,0,0,0,0,1,3,1,1,4,nt=300 way= 57
0,0,0,0,0,0,1,3,1,0,6,nt=300 way= 58
!!!!!where=9
!!!!!where=10
0,0,0,0,0,0,1,3,0,5,0,nt=300 way= 59
0,0,0,0,0,0,1,3,0,4,2,nt=300 way= 60
0,0,0,0,0,0,1,3,0,3,4,nt=300 way= 61
0,0,0,0,0,0,1,3,0,2,6,nt=300 way= 62
0,0,0,0,0,0,1,3,0,1,8,nt=300 way= 63
0,0,0,0,0,0,1,3,0,0,10,nt=300 way= 64
!!!!!where=9
!!!!!where=10
!!!!!where=8
!!!!!where=9
!!!!!where=10
0,0,0,0,0,0,1,2,5,0,0,nt=300 way= 65
0,0,0,0,0,0,1,2,4,2,0,nt=300 way= 66
0,0,0,0,0,0,1,2,4,1,2,nt=300 way= 67
0,0,0,0,0,0,1,2,4,0,4,nt=300 way= 68
!!!!!where=9
!!!!!where=10
0,0,0,0,0,0,1,2,3,4,0,nt=300 way= 69
0,0,0,0,0,0,1,2,3,3,2,nt=300 way= 70
0,0,0,0,0,0,1,2,3,2,4,nt=300 way= 71
0,0,0,0,0,0,1,2,3,1,6,nt=300 way= 72
0,0,0,0,0,0,1,2,3,0,8,nt=300 way= 73
!!!!!where=9
!!!!!where=10
0,0,0,0,0,0,1,2,2,6,0,nt=300 way= 74
0,0,0,0,0,0,1,2,2,5,2,nt=300 way= 75
0,0,0,0,0,0,1,2,2,4,4,nt=300 way= 76
0,0,0,0,0,0,1,2,2,3,6,nt=300 way= 77
0,0,0,0,0,0,1,2,2,2,8,nt=300 way= 78
0,0,0,0,0,0,1,2,2,1,10,nt=300 way= 79
0,0,0,0,0,0,1,2,2,0,12,nt=300 way= 80
!!!!!where=9
!!!!!where=10
0,0,0,0,0,0,1,2,1,8,0,nt=300 way= 81
0,0,0,0,0,0,1,2,1,7,2,nt=300 way= 82
0,0,0,0,0,0,1,2,1,6,4,nt=300 way= 83
0,0,0,0,0,0,1,2,1,5,6,nt=300 way= 84
0,0,0,0,0,0,1,2,1,4,8,nt=300 way= 85
0,0,0,0,0,0,1,2,1,3,10,nt=300 way= 86
0,0,0,0,0,0,1,2,1,2,12,nt=300 way= 87
0,0,0,0,0,0,1,2,1,1,14,nt=300 way= 88
0,0,0,0,0,0,1,2,1,0,16,nt=300 way= 89
!!!!!where=9
!!!!!where=10
0,0,0,0,0,0,1,2,0,10,0,nt=300 way= 90
0,0,0,0,0,0,1,2,0,9,2,nt=300 way= 91
0,0,0,0,0,0,1,2,0,8,4,nt=300 way= 92
0,0,0,0,0,0,1,2,0,7,6,nt=300 way= 93
0,0,0,0,0,0,1,2,0,6,8,nt=300 way= 94
0,0,0,0,0,0,1,2,0,5,10,nt=300 way= 95
0,0,0,0,0,0,1,2,0,4,12,nt=300 way= 96
0,0,0,0,0,0,1,2,0,3,14,nt=300 way= 97
0,0,0,0,0,0,1,2,0,2,16,nt=300 way= 98
0,0,0,0,0,0,1,2,0,1,18,nt=300 way= 99
0,0,0,0,0,0,1,2,0,0,20,nt=300 way= 100
!!!!!where=9
!!!!!where=10
!!!!!where=8
!!!!!where=9
!!!!!where=10
0,0,0,0,0,0,1,1,7,1,0,nt=300 way= 101
x,x,x,x,x,x,x,x,x,0,y bug  for way~~~~~~~
0,0,0,0,0,0,1,1,6,3,0,nt=300 way= 103
0,0,0,0,0,0,1,1,6,2,2,nt=300 way= 104
0,0,0,0,0,0,1,1,6,1,4,nt=300 way= 105
0,0,0,0,0,0,1,1,6,0,6,nt=300 way= 106
!!!!!where=9
!!!!!where=10
0,0,0,0,0,0,1,1,5,5,0,nt=300 way= 107
0,0,0,0,0,0,1,1,5,4,2,nt=300 way= 108
0,0,0,0,0,0,1,1,5,3,4,nt=300 way= 109
0,0,0,0,0,0,1,1,5,2,6,nt=300 way= 110
0,0,0,0,0,0,1,1,5,1,8,nt=300 way= 111
0,0,0,0,0,0,1,1,5,0,10,nt=300 way= 112
!!!!!where=9
!!!!!where=10
0,0,0,0,0,0,1,1,4,7,0,nt=300 way= 113
0,0,0,0,0,0,1,1,4,6,2,nt=300 way= 114
0,0,0,0,0,0,1,1,4,5,4,nt=300 way= 115
0,0,0,0,0,0,1,1,4,4,6,nt=300 way= 116
0,0,0,0,0,0,1,1,4,3,8,nt=300 way= 117
0,0,0,0,0,0,1,1,4,2,10,nt=300 way= 118
0,0,0,0,0,0,1,1,4,1,12,nt=300 way= 119
0,0,0,0,0,0,1,1,4,0,14,nt=300 way= 120
!!!!!where=9
!!!!!where=10
0,0,0,0,0,0,1,1,3,9,0,nt=300 way= 121
0,0,0,0,0,0,1,1,3,8,2,nt=300 way= 122
0,0,0,0,0,0,1,1,3,7,4,nt=300 way= 123
0,0,0,0,0,0,1,1,3,6,6,nt=300 way= 124
0,0,0,0,0,0,1,1,3,5,8,nt=300 way= 125
0,0,0,0,0,0,1,1,3,4,10,nt=300 way= 126
0,0,0,0,0,0,1,1,3,3,12,nt=300 way= 127
0,0,0,0,0,0,1,1,3,2,14,nt=300 way= 128
0,0,0,0,0,0,1,1,3,1,16,nt=300 way= 129
0,0,0,0,0,0,1,1,3,0,18,nt=300 way= 130
!!!!!where=9
!!!!!where=10
0,0,0,0,0,0,1,1,2,11,0,nt=300 way= 131
0,0,0,0,0,0,1,1,2,10,2,nt=300 way= 132
0,0,0,0,0,0,1,1,2,9,4,nt=300 way= 133
0,0,0,0,0,0,1,1,2,8,6,nt=300 way= 134
0,0,0,0,0,0,1,1,2,7,8,nt=300 way= 135
0,0,0,0,0,0,1,1,2,6,10,nt=300 way= 136
0,0,0,0,0,0,1,1,2,5,12,nt=300 way= 137
0,0,0,0,0,0,1,1,2,4,14,nt=300 way= 138
0,0,0,0,0,0,1,1,2,3,16,nt=300 way= 139
0,0,0,0,0,0,1,1,2,2,18,nt=300 way= 140
0,0,0,0,0,0,1,1,2,1,20,nt=300 way= 141
0,0,0,0,0,0,1,1,2,0,22,nt=300 way= 142
!!!!!where=9
!!!!!where=10
0,0,0,0,0,0,1,1,1,13,0,nt=300 way= 143
0,0,0,0,0,0,1,1,1,12,2,nt=300 way= 144
0,0,0,0,0,0,1,1,1,11,4,nt=300 way= 145
0,0,0,0,0,0,1,1,1,10,6,nt=300 way= 146
0,0,0,0,0,0,1,1,1,9,8,nt=300 way= 147
0,0,0,0,0,0,1,1,1,8,10,nt=300 way= 148
0,0,0,0,0,0,1,1,1,7,12,nt=300 way= 149
0,0,0,0,0,0,1,1,1,6,14,nt=300 way= 150
0,0,0,0,0,0,1,1,1,5,16,nt=300 way= 151
0,0,0,0,0,0,1,1,1,4,18,nt=300 way= 152
0,0,0,0,0,0,1,1,1,3,20,nt=300 way= 153
0,0,0,0,0,0,1,1,1,2,22,nt=300 way= 154
0,0,0,0,0,0,1,1,1,1,24,nt=300 way= 155
0,0,0,0,0,0,1,1,1,0,26,nt=300 way= 156
!!!!!where=9
!!!!!where=10
0,0,0,0,0,0,1,1,0,15,0,nt=300 way= 157
0,0,0,0,0,0,1,1,0,14,2,nt=300 way= 158
0,0,0,0,0,0,1,1,0,13,4,nt=300 way= 159
0,0,0,0,0,0,1,1,0,12,6,nt=300 way= 160
0,0,0,0,0,0,1,1,0,11,8,nt=300 way= 161
0,0,0,0,0,0,1,1,0,10,10,nt=300 way= 162
0,0,0,0,0,0,1,1,0,9,12,nt=300 way= 163
0,0,0,0,0,0,1,1,0,8,14,nt=300 way= 164
0,0,0,0,0,0,1,1,0,7,16,nt=300 way= 165
0,0,0,0,0,0,1,1,0,6,18,nt=300 way= 166
0,0,0,0,0,0,1,1,0,5,20,nt=300 way= 167
0,0,0,0,0,0,1,1,0,4,22,nt=300 way= 168
0,0,0,0,0,0,1,1,0,3,24,nt=300 way= 169
0,0,0,0,0,0,1,1,0,2,26,nt=300 way= 170
0,0,0,0,0,0,1,1,0,1,28,nt=300 way= 171
0,0,0,0,0,0,1,1,0,0,30,nt=300 way= 172
!!!!!where=9
!!!!!where=10
!!!!!where=8
!!!!!where=9
!!!!!where=10
0,0,0,0,0,0,1,0,10,0,0,nt=300 way= 173
0,0,0,0,0,0,1,0,9,2,0,nt=300 way= 174
0,0,0,0,0,0,1,0,9,1,2,nt=300 way= 175
0,0,0,0,0,0,1,0,9,0,4,nt=300 way= 176
!!!!!where=9
!!!!!where=10
0,0,0,0,0,0,1,0,8,4,0,nt=300 way= 177
0,0,0,0,0,0,1,0,8,3,2,nt=300 way= 178
0,0,0,0,0,0,1,0,8,2,4,nt=300 way= 179
0,0,0,0,0,0,1,0,8,1,6,nt=300 way= 180
0,0,0,0,0,0,1,0,8,0,8,nt=300 way= 181
!!!!!where=9
!!!!!where=10
0,0,0,0,0,0,1,0,7,6,0,nt=300 way= 182
0,0,0,0,0,0,1,0,7,5,2,nt=300 way= 183
0,0,0,0,0,0,1,0,7,4,4,nt=300 way= 184
0,0,0,0,0,0,1,0,7,3,6,nt=300 way= 185
0,0,0,0,0,0,1,0,7,2,8,nt=300 way= 186
0,0,0,0,0,0,1,0,7,1,10,nt=300 way= 187
0,0,0,0,0,0,1,0,7,0,12,nt=300 way= 188
!!!!!where=9
!!!!!where=10
0,0,0,0,0,0,1,0,6,8,0,nt=300 way= 189
0,0,0,0,0,0,1,0,6,7,2,nt=300 way= 190
0,0,0,0,0,0,1,0,6,6,4,nt=300 way= 191
0,0,0,0,0,0,1,0,6,5,6,nt=300 way= 192
0,0,0,0,0,0,1,0,6,4,8,nt=300 way= 193
0,0,0,0,0,0,1,0,6,3,10,nt=300 way= 194
0,0,0,0,0,0,1,0,6,2,12,nt=300 way= 195
0,0,0,0,0,0,1,0,6,1,14,nt=300 way= 196
0,0,0,0,0,0,1,0,6,0,16,nt=300 way= 197
!!!!!where=9
!!!!!where=10
0,0,0,0,0,0,1,0,5,10,0,nt=300 way= 198
0,0,0,0,0,0,1,0,5,9,2,nt=300 way= 199
0,0,0,0,0,0,1,0,5,8,4,nt=300 way= 200
press 'enter' to continue
``````

### Stack Overflow

Posted: Wed Mar 02, 2005 6:21 am
plz help

i think i can solve
but Stack Overflow

i use MS VC++
if i use ctrl+F5
run program normally(looks normally,no result)

if in debug,he say
Unheandled exception in win.exe: 0xc00000FD: Stack Overflow

i can only solve the problem under 500(5.00)

i try to change 'int way' and 'int coin_mount[N]'
to long,but no use

Code: Select all

``````
/*
right ans
1.00                50
2.00               293
3.00              1022
4.00              2728
5.00              6149
6.00             12368
50.00         513269191
*/

#include <iostream>
#include <string>
using namespace std;
#define N 11
//#define OUTPUT 1

int Dollars(const int value[N],long coin_mount[N],
const int &target,
int where,int way,int counter)
{
int i,gether=0,howmany=0
,left=target;
int amount=0;

for(i=where;i<N;i++)
{
if(value[i]<=left && left>0 )
{
where=i;	//find the tail
coin_mount[i]=left/value[i];
left=target%value[i];
}
else
{
coin_mount[i]=0;
}
}
#ifdef OUTPUT
for(i=0;i<N;i++)
{
if(coin_mount[i])
{
amount+=coin_mount[i]*value[i];
}
cout<<coin_mount[i]<<",";
}
cout<<" NT="<<amount;
cout<<endl;
#endif

for(int i2=where;i2>=0;i2--)
{

if(i2==N-1)
{
continue;
}
if(coin_mount[i2])
{
coin_mount[i2]--;
int target2=value[i2];
for(int i5=i2+1;i5<N;i5++)
{
target2+=coin_mount[i5]*value[i5];
}
return Dollars(value,coin_mount,target2,i2+1,way+1,0);
//i2 is where in this recursion
}
else
{
if(i2==0 && coin_mount[0]==0)
{
return way+1;
}
}
}

}

int main()
{
int value[N]={10000, 5000, 2000, 1000, 500,200
, 100, 50, 20, 10 ,5};
int target=600;
//target*=100;
//set target as input~~
long coin_mount[N]={0};

if(target==0) cout<<"1";

int ans=Dollars(value,coin_mount,target,0,0,0);
cout<<ans<<endl;

return 0;
}

``````

Posted: Wed Mar 02, 2005 6:34 am
PS: My input and output

/*
My input
1===>target=100
2===>target=200
3
4
5
6

output
50 right!!
293 right!!
1022 right!!
2728 right!!
6149 right!!
Overflow

right ans
1.00 50
2.00 293
3.00 1022
4.00 2728
5.00 6149
6.00 12368
50.00 513269191
*/

### 147Floating point exception

Posted: Sat Mar 05, 2005 1:52 am
Your program has died with signal 8 (SIGFPE). Meaning:

Floating point exception

Before crash, it ran during 0.002 seconds.

Code: Select all

``````#include <iostream>
#include <iomanip>
using namespace std;
#define N 11

void output(int coin_mount[N],const int value[N],int way,int count)
{
int mount=0;
for(int i=N-1;i>=0;i--)
{
mount+=coin_mount[i]*value[i];
cout<<coin_mount[i]<<",";
}
cout<<" NT= "<<mount<<" cc= "<<count<<" way= "<<way<<endl;
}
int main()
{
const int value[N]={5,10,20,50,100,200
,500,1000,2000,5000,10000};
int way=0;
int coin_mount[N]={0};
float keyin=0;
int count=0;
int i2,i3,i7;
bool over;
cout.setf(ios::fixed,ios::floatfield);

do{
cin>>keyin;
if(keyin==0.00) return 0;
cout.width(6);
cout.precision(2);
cout<<keyin;
count=0;

over=false;
int target=(int)(keyin*100);
int where=1;
int left=target;
way=0;
for(i7=0;i7<N;i7++)coin_mount[i7]=0;
do
{

int i=0;
if(left==0)
{
way++;
//count++;
//output(coin_mount,value,way,count);
}
do
{
if(left)
{
coin_mount[i]=left/value[i];
left=left%value[i];
i++;
way++;
//count++;
//output(coin_mount,value,way,count);
}
}while(left);

do
{
if(coin_mount[0]*value[0]>=value[1])
{//
int temp=(coin_mount[0]*value[0])/value[1];
coin_mount[0]=0;//omlu for value[0]==5 value[1]==10
coin_mount[1]+=temp;
way+=temp;
//count++;
//output(coin_mount,value,way,count);

}
else
{
break;
}
}while(true);

int amount=0;
for(i2=1;i2<N;i2++)
{
if(amount>=value[i2])
{
left=target;
coin_mount[i2]++;
for(i3=0;i3<N;i3++)
{
if(i3<i2)
{
coin_mount[i3]=0;
}
else if(coin_mount[i3])
{
left-=(value[i3]*coin_mount[i3]);
}

}
break;
}
else
{
amount+=value[i2]*coin_mount[i2];
}
if(i2==N-1)
{
break;
}
}

if(i2==N-1)
{

cout<<setw(17)<<setiosflags(ios::right)
<<way<<endl;
break;
}

}while(true);
}while(keyin!=0.00);
return 0;
}

``````

### P147 - Why WA?

Posted: Tue May 10, 2005 8:25 pm
I'm solving it with DP.
In my PC N = 120.00 my code gives negative number, but I don't know why.
Here is my code:

Code: Select all

``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main (void) {
long long I, J, N, A [6001], C [] = {1, 2, 4, 10, 20, 40, 100, 200, 400, 1000, 4000};
double M;
N = 6000;
memset (A, 0, sizeof (A));
A [0] = 1;
for (I = 0; I < 11; I++)
for (J = C [I]; J <= N; J++) A [J] = (long long)A [J]+A [J-C [I]];
while (scanf ("%lf", &M)) {
if (M == 0) break;
printf ("%6.2lf", M);
N = (long long)(100*M+0.5), N /= 5;
printf ("%18.ld\n", A [N]);
}
exit (0);
}``````
PLZZZ HELPPP.

Posted: Wed May 11, 2005 4:51 am
try %lld for long long

(%I64d for MS compiler, but don't submit it like that)

### Again WA.

Posted: Wed May 11, 2005 4:30 pm
It gets again WA.

Posted: Wed May 11, 2005 5:18 pm
Shouldn't the last number in your C[] array be 2000? Since, \$100 = 2000 * \$.05.

### I got AC.

Posted: Thu May 12, 2005 12:59 pm
mf

THX, I got AC .

Posted: Tue May 31, 2005 4:42 pm
Thnx ... I've restructured my algo because of this