147 - Dollars

Sanny · Post by **Sanny** » 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

sklitzz · Post by **sklitzz** » 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 )

#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;
}

sklitzz · Post by **sklitzz** » 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;
}

sklitzz · Post by **sklitzz** » Tue Feb 15, 2005 7:29 pm

Never mind this post I sollved the problem

58050zz · Post by **58050zz** » Mon Feb 28, 2005 5:24 pm

please help~~

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

58050zz · Post by **58050zz** » 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;
}

58050zz · Post by **58050zz** » 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
*/

58050zz · Post by **58050zz** » 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;
}

KvaLe · Post by **KvaLe** » 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.

Quantris · Post by **Quantris** » Wed May 11, 2005 4:51 am

try %lld for long long

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

KvaLe · Post by **KvaLe** » Wed May 11, 2005 4:30 pm

It gets again WA.

mf · Post by mf » Wed May 11, 2005 5:18 pm

Shouldn't the last number in your C[] array be 2000? Since, $100 = 2000 * $.05.

KvaLe · Post by **KvaLe** » Thu May 12, 2005 12:59 pm

mf

THX, I got AC

.

[_TANG_] · Post by **[_TANG_]** » Tue May 31, 2005 4:42 pm

Thnx ... I've restructured my algo because of this

cOsMo · Post by **cOsMo** » Wed Jun 08, 2005 1:22 am

CODE REMOVED

OJ Board

147 - Dollars

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

147 bug

Stack Overflow

147Floating point exception

P147 - Why WA?

Again WA.

I got AC.

147 __int64 can't hold big results.Please help