357 - Let Me Count The Ways

[Ming Han]

I managed to solve this question before but forogt to delete the message.

Thanks anyway. Happy programming.

[Ronaldo]

[cpp]

Code: Select all

This is my code !!!

#include<iostream.h>
#include<stdio.h>

long ans[100][6];  
int a[6]; 
double r; 

int i,n,k,j; 
long m; 
void findans()
{
long s; 
 
a[1]=1;a[2]=5;a[3]=10;a[4]=25;a[5]=50; 
for (i=1;i<6;i++) 
  for (j=1;j<100;j++)
  {
    if (j<a[i])
		ans[j][i]=0;
	else
	{
     if(j==a[i])
		 ans[j][i]=1;
	 else 
	 { 
       s=0; 
       for( k=1 ;k<=i;k++)
		   s=s+ans[j-a[i]][k]; 
       ans[j][i]=s; 
	 }
	}
  }
}
int main()
{
   
  findans(); 
  while (cin>>n)
  {
    m=0; 
    for(i=1;i<6;i++)
		m=m+ans[n][i];
	if(m!=1)
		cout<<"There are "<<m<<" ways to produce "<<n<<" cents change.\n";
    else
	cout<<"There is only 1 way to produce "<<n<<" cents change.\n";
    
  }
  return 0;
} 
[color=red][/color][color=#444444][/color]

[/cpp]

[problem]

here is my code.wa.plz help me.
[c]

#include<stdio.h>
#include<math.h>

#define SIZE 5
#define SIZE1 7500



void main()
{
long int store[SIZE]={1,5,10,25,50};
long int count[SIZE1],inp;
long int i,j,temp;

while(scanf("%ld",&inp)==1)
{

if(inp==0)
{
printf("There is only 1 way to produce %ld cents change.\n");
continue;
}

count[store[0]]=1;


for(i=2;i<=inp;i++)
count=0;

for(i=0;store<=inp&&i<SIZE;i++)
for(j=store;j<=inp;j++)
{
temp=j-store ;
count[j]=count[j]+count[temp];
}
printf("There are %ld ways to produce %ld cents change.\n",count[j-1],inp);
}
}
[\c]

[Frostina]

please help me .... lol

[cpp]
#include <iostream>
using namespace std;
int main() {
int change[100];
int i;
for (i=0;i<100;i++) change = 1;
for (i=5;i<100;i++) change+=change[i-5];
for (i=10;i<100;i++) change+=change[i-10];
for (i=25;i<100;i++) change+=change[i-25];
for (i=50;i<100;i++) change+=change[i-50];
while (cin>>i){ // must 0<=i<99
if (change==1)
cout << "There is only 1 way to produce " << i << " cents change." << endl;
else
cout << "There are " << change << " ways to produce " << i << " cents change. " << endl;
}
return 0;
}
[/cpp]

[sohel]

For this problem the judge data and the problem statement has been changed. The new range of input is 30000.
Your program is correct. Simply change the array size to 30001 and make sure it is (long long) type.

[Frostina]

Thank you very much .... ^^y

Now I get AC ...^^

[Eduard]

Problem input is biger like 30000 yes?
This problem is a big number problem yes?
I thing that just when input is 8000 then answer must be 1500000000 like this, it means that when input is 30000 then answer must have more than 30 digits yes?

[sohel]

Hi Eduard,
You must have miscalculated something in your approach.
I used long long and it supports the answer for 30000.

[Eduard]

Yes you are rigth i use c++ long long and get AC.
But i thing this problem can't be solved by pascal without using big numbers.
Thanks.

[anupam]

I used Bigint program written by me and got ac within time . I used double data ype and got ac also. So pascal programmers, I thik, will not face problems. At least Bigint programs are available..
--
Anupam

[rasel04]

I use long long int .But why I always got wrong answer? Please see my code and find the bug.

Code: Select all

#include<stdio.h>


int coin[10]={0,1,5,10,25,50};
long long int ways[30005][7];

void main()
{

	int N,i,j;
	for(i=1;i<=30000;i++) ways[i][0]=0;
	for(i=1;i<=5;i++) ways[0][i]=1;
	
	for(i=1;i<=30000;i++)
	{
		for(j=1;j<=5;j++)
		{
			if((i-coin[j])<0)
				ways[i][j]=ways[i][j-1];
			else 
				ways[i][j]=ways[i][j-1]+ways[i-coin[j]][j];
		}		
	}

	while(scanf("%d",&N)==1)
	{
		if(N==0)
		{
			printf("There are 0 way to produce 0 cents change.\n");
			continue;
		}
		
		if(ways[N][5]==1) printf("There is only 1 way to produce %d cents change.\n",N);
		else printf("There are %lld ways to produce %d cents change.\n",ways[N][5],N);	
	}
}

[rasel04]

I got accepted . I done a stupid mistake for the first case. I fixed my mistake and got accepted.

[Klechu]

I think your code is correct but the size of table is not 7500 (like in task 612) but 30000 ;)

[Klechu]

Hi all
When I use long long data type in my C program I get Runtime Error (SIGSEGV) - what is that & what can I do with that ?
Thank you for all help

Klechu

[sohel]

long long is not the cause of RTE....... this type of RTE results from accessing index of an array beyond its size and etc.

Why don't you post your code......... it will be easier to identify the cause of the error.