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

chinmoy kanti dhar
New poster
Posts: 19
Joined: Fri Jun 22, 2007 6:17 pm

wr

give some input output plz?

30000= 543427145501
20000= 107683177001
0=1
is these output are right?

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Your cases are correct. You can post your code.
Ami ekhono shopno dekhi...
HomePage

chinmoy kanti dhar
New poster
Posts: 19
Joined: Fri Jun 22, 2007 6:17 pm

help me

but i am getting wrong answer.here is the code-

[code]
cut after AC
[/code]
Last edited by chinmoy kanti dhar on Tue Aug 21, 2007 6:52 pm, edited 1 time in total.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
You don't even pass the sample test case..
See the output description carefully..

tuman
New poster
Posts: 24
Joined: Sat Oct 22, 2005 7:30 pm
Location: CUET
Contact:
Handle "are" "is" carefully.
You code is ok. it will get accepted.
Ur logic is cool. just change it and dont need to change ur logic at all.....
dont do coding while sleeping :wink

somebody could have helped u b4 by telling that silly mistake rather than making fun out of sample output. This kindah fault is really annoying....
Last edited by tuman on Tue Aug 21, 2007 7:02 pm, edited 1 time in total.
We the dreamer of the dreamy dream...

chinmoy kanti dhar
New poster
Posts: 19
Joined: Fri Jun 22, 2007 6:17 pm
thanks.now i have accepted it.

rhsumon
New poster
Posts: 48
Joined: Wed Aug 23, 2006 12:29 pm
Location: Dhaka

TLE - 357

Why Time L E Plz ...........

Code: Select all

``````#include <stdio.h>
#define MAXTOTAL 30000
long long  nway[MAXTOTAL+5];
int coin[5] = { 50,25,10,5,1 };

void main()
{
int i,j,n,v,c;
while(scanf("%d",&n) == 1){
for(i=0; i<=n; i++) nway[i] = 0;
v = 5;
nway[0] = 1;
for (i=0; i<v; i++){
c = coin[i];
for (j=c; j<=n; j++)
nway[j] += nway[j-c];
}
printf("There are %lld ways to produce %d cents change.\n",nway[n],n);
}
}
``````

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Just precalculate all. Then take input show the calculated result. [You are taking input and then calculating.]
Ami ekhono shopno dekhi...
HomePage

ishtiaq ahmed
Learning poster
Posts: 53
Joined: Sat Jul 29, 2006 7:33 am

357 Let Me Count The Ways[compilation error]

This program is compilation error. can anyone help me? Here is my code

Code: Select all

``````The code is removed after AC. Thanks for replying.
``````
Last edited by ishtiaq ahmed on Wed Sep 12, 2007 7:21 am, edited 2 times in total.
No venture no gain

with best regards
------------------------
ishtiaq ahmed

Bappi_cuet
New poster
Posts: 14
Joined: Wed Jul 11, 2007 4:26 pm
Location: CSE, CUET. Chittagong, Bangladesh.
Contact:
replace void main() to int main(). Hope its help.
---------------------------------------------
IT'S TIME TO GO AHEAD !!!!
---------------------------------------------

WingletE
New poster
Posts: 35
Joined: Sun Aug 13, 2006 1:34 pm
Location: Taipei, Taiwan
Contact:

Re: 357 WA

txandi wrote: long long int total[MAX+1];

total[0]=1;
for(int i=0;i<5;i++)
{
...
}
...
Why isn't it necessary to set all the elements in 'total' to zero before using it?

andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Re: 357 WA

WingletE wrote:
txandi wrote: long long int total[MAX+1];

total[0]=1;
for(int i=0;i<5;i++)
{
...
}
...
Why isn't it necessary to set all the elements in 'total' to zero before using it?
Because all values in an array are defaulted to 0. For instance, if you run this code

Code: Select all

``````#include <iostream>
using namespace std;
int a[10];
int main(){
for (int i=0; i<10; ++i) cout << a[i] << " ";
cout << endl;
return 0;
}``````
you will get

Code: Select all

``0 0 0 0 0 0 0 0 0 0 ``
as an output.

Now, I need a little help in understanding this dynamic programming solution. I can't see how it works.

I know dynamic programming is simply used to avoid recalculating repeated operations, so there must exist a recursive function that gives me the solution of this problem.

Let f(n) be a function that returns the number of ways you can make n cents (i.e, the solution for n). How can I define f(n) in terms of f(n-i)? i.e, how can I define f(n) in a recursive way?

Thanks!
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

Re: 357 WA

I don't know why it doesn't work for 30000. someone please help me.

Code: Select all

``Accepted Now``
Last edited by Obaida on Thu May 22, 2008 1:41 pm, edited 1 time in total.
try_try_try_try_&&&_try@try.com
This may be the address of success.

andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Re: 357 WA

You have two bugs:

1. You should change the definition of the array ways from long to long long.
2. You are using <=MAX in your loops, but in the worst case MAX can be 30001 and you would have problems because the array ways has only 30001 positions, that is, it has position from index 0 to index 30000; index 30001 would be using memory that doesn't belong to the array.

You can fix both problems by changing:

Code: Select all

``````#define MAX 30001
long ways[MAX];``````
to

Code: Select all

``````#define MAX 30000
long long ways[MAX+1];``````
You also need to manage the case of only one way to get accepted.

Good luck!
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
``Thanks Andmej I got Accepted``