## 357 - Let Me Count The Ways

Moderator: Board moderators

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

### Thx

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]

[cpp]

Code: Select all

``````This is my code !!!

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

long ans;
int a;
double r;

int i,n,k,j;
long m;
void findans()
{
long s;

a=1;a=5;a=10;a=25;a=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

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]=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?

[cpp]
#include <iostream>
using namespace std;
int main() {
int change;
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
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
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

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
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
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. 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:
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

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={0,1,5,10,25,50};
long long int ways;

void main()
{

int N,i,j;
for(i=1;i<=30000;i++) ways[i]=0;
for(i=1;i<=5;i++) ways[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]==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],N);
}
}
``````

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

### 357 - Accepted

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

Klechu
New poster
Posts: 8
Joined: Fri Apr 16, 2004 6:27 pm
Location: Rzesz
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

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

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. 