Greedy is in ch16Raj Ariyan wrote: Try to read this book when u will free. It will help you much. Greedy most probably in chapter 16.
do i use Greedy to slove this?
to sohel:
my code is not AC is TLE^^
Moderator: Board moderators
Greedy is in ch16Raj Ariyan wrote: Try to read this book when u will free. It will help you much. Greedy most probably in chapter 16.
i use ur algorithm and slove ok for 674sohel wrote:Hi,
From your code it looks like you are using brute force. And that should obviously get TLE.
Implementation of DP:
1) declare an int array of size 7500
2) initialize all the elements with 0
3) set Array[0] = 1; --- because there is only one way of making zero ie
'by not choosing any coin'.
4) for every coin run a loop from j = 1 to 7500
set Array[ coinvalue + j] += Array[j];
5) END
Hope it helps.
I think the error could be in handling the conversion of floating point number to integer.58050zz wrote:
while(cin>>target)
{
cout.width(6);
cout.precision(2);
cout<<target;
if(target==0)return 0;
int tar=(int)(target*100);
cout<<setw(17)<<setiosflags(ios::right)
<<Array[tar]<<endl;
}
Code: Select all
while(scanf("%d", &n) != 0)
printf("%d\n", dp[n]);
Code: Select all
#include<stdio.h>/* 674 357 147*/
int main(){
int a[30001][4],t;
int i,tol,n;
for(i=0;i<5;i++){
a[i][0]=0;
a[i][1]=0;
a[i][2]=0;
a[i][3]=0;
}
tol=4;
while( scanf("%d",&n)!=EOF ){
if(n>tol){
for( ; tol<=n ;tol++){
if( tol>=50)
a[tol][0]=a[tol-50][0]+a[tol-50][1]+a[tol-50][2]+a[tol-50][3]+1;
else
a[tol][0]=0;
if( tol>=25)
a[tol][1]=a[tol-25][1]+a[tol-25][2]+a[tol-25][3]+1;
else
a[tol][1]=0;
if( tol>=10)
a[tol][2]=a[tol-10][2]+a[tol-10][3]+1;
else
a[tol][2]=0;
if( tol>=5)
a[tol][3]=a[tol-5][3]+1;
else
a[tol][3]=0;
}
}
t=a[n][0]+a[n][1]+a[n][2]+a[n][3]+1;
printf("%d\n",t);
/*if(t!=1)
printf("There are %d ways to produce %d cents change. \n",t,n);
else
printf("There are 1 way to produce %d cents change. \n",n);*/
}
return 0;
}
Code: Select all
5
6
Code: Select all
2
2
Code: Select all
edited afer AC
Code: Select all
#include<stdio.h>
#include<iostream.h>
#include<string.h>
int cent_1(int mon);
int cent_5(int mon);
int cent_10(int mon);
int cent_25(int mon);
int cent_50(int mon);
int count=0;
int main(void)
{
int cent, sum;
while(scanf("%d",¢)!=EOF)
{
count=0;
if(cent>=1 && cent<=4)
{
printf("%d\n",cent_1(cent));
}
if(cent>=5 && cent<=9)
{
sum=0;
if(cent==5)
sum=1;
sum+=cent_1(cent);
sum+=cent_5(cent);
printf("%d\n",sum);
}
if(cent>=10 && cent<=24)
{
sum=0;
if(cent==10)
sum+=1;
sum+=cent_1(cent);
sum+=cent_5(cent);
sum+=cent_10(cent);
printf("%d\n",sum);
}
if(cent>=25 && cent<=49)
{
sum=0;
if(cent==25)
sum+=1;
sum+=cent_1(cent);
sum+=cent_5(cent);
sum+=cent_10(cent);
sum+=cent_25(cent);
printf("%d\n",sum);
}
if(cent>=50)
{
sum=0;
if(cent==50)
sum+=1;
sum+=cent_1(cent);
sum+=cent_5(cent);
sum+=cent_10(cent);
sum+=cent_25(cent);
sum+=cent_50(cent);
printf("%d\n",sum);
}
}
}
int cent_1( int mon)
{
if(mon==0)
return 0;
return 1;
}
int cent_5( int mon)
{
int i,m,t=0,temp;
if(mon==0)
return 0;
m=mon/5;
for(i=m; i>0; i--)
{
temp=mon-5*i;
t=t+cent_1(temp);
}
return t;
}
int cent_10( int mon)
{
int i,m,t=0,temp;
if(mon==0)
return 0;
m=mon/10;
for(i=m; i>0; i--)
{
temp=mon-10*i;
t=t+cent_1(temp);
}
for(i=m; i>0; i--)
{
temp=mon-10*i;
t=t+cent_5(temp);
}
return t;
}
int cent_25( int mon)
{
int i,m,t=0,temp;
if(mon==0)
return 0;
m=mon/25;
for(i=m; i>0; i--)
{
temp=mon-25*i;
t=t+cent_1(temp);
}
for(i=m; i>0; i--)
{
temp=mon-25*i;
t=t+cent_5(temp);
}
for(i=m; i>0; i--)
{
temp=mon-25*i;
t=t+cent_10(temp);
}
return t;
}
int cent_50( int mon)
{
int i,m,t=0,temp;
if(mon==0)
return 0;
m=mon/50;
for(i=m; i>0; i--)
{
temp=mon-50*i;
t=t+cent_1(temp);
}
for(i=m; i>0; i--)
{
temp=mon-50*i;
t=t+cent_5(temp);
}
for(i=m; i>0; i--)
{
temp=mon-50*i;
t=t+cent_10(temp);
}
for(i=m; i>0; i--)
{
temp=mon-50*i;
t=t+cent_25(temp);
}
return t;
}