357 - Let Me Count The Ways

All about problems in Volume 3. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Ming Han
Learning poster
Posts: 77
Joined: Thu Jun 06, 2002 7:10 pm
Location: Singapore
Contact:

Thx

Post by Ming Han »

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

Thanks anyway. Happy programming.
:: HanWorks ::

Ronaldo
New poster
Posts: 5
Joined: Fri May 23, 2003 1:45 pm

[b] 357 Why WA?[/b]

Post by 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
New poster
Posts: 27
Joined: Mon Nov 10, 2003 12:40 am

357 help me plz

Post by 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
New poster
Posts: 23
Joined: Mon Dec 15, 2003 5:21 am

#357 .. Why runtime error T____T?

Post by 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]
Thanks for your help ! ;)

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by 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
New poster
Posts: 23
Joined: Mon Dec 15, 2003 5:21 am

Post by Frostina »

Thank you very much .... ^^y

Now I get AC ...^^
Thanks for your help ! ;)

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

357

Post by 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?
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel »

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

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by 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. :D
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by 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
"Everything should be made simple, but not always simpler"

rasel04
New poster
Posts: 9
Joined: Sun Dec 07, 2003 4:52 am

357- WA

Post by 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
New poster
Posts: 9
Joined: Sun Dec 07, 2003 4:52 am

357 - Accepted

Post by rasel04 »

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

Klechu
New poster
Posts: 8
Joined: Fri Apr 16, 2004 6:27 pm
Location: Rzesz

Post by Klechu »

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

Klechu
New poster
Posts: 8
Joined: Fri Apr 16, 2004 6:27 pm
Location: Rzesz

357 ->Sigsegv

Post by 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
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

not long long

Post by 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. :-?

Post Reply

Return to “Volume 3 (300-399)”