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
Location: bangladesh

wr

Post by chinmoy kanti dhar »

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
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

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
Location: bangladesh

help me

Post by chinmoy kanti dhar »

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

Post by helloneo »

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:

Post by tuman »

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
Location: bangladesh

Post by chinmoy kanti dhar »

thanks.now i have accepted it.

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

TLE - 357

Post by rhsumon »

Anyone say about this.........
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
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

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
Location: (CSE,DU), Dhaka,Bangladesh

357 Let Me Count The Ways[compilation error]

Post by ishtiaq ahmed »

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:

Post by Bappi_cuet »

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

Post by WingletE »

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

Post by andmej »

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
Location: (BUBT) Dhaka,Bagladesh.

Re: 357 WA

Post by Obaida »

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

Post by andmej »

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
Location: (BUBT) Dhaka,Bagladesh.

Re: 357 WA

Post by Obaida »

Code: Select all

Thanks Andmej I got Accepted
Sometimes I did such kind of mistake I didn't checked my output with the sample case carefully.
Thank you again :) ! Hope to be careful in future.
try_try_try_try_&&&_try@try.com
This may be the address of success.

Post Reply

Return to “Volume 3 (300-399)”