OJ Board

Posted: **Thu Aug 12, 2004 8:29 pm**

Hi, I think i have almost solved the problem, but i need some I/O data because I got WA, I think the error is small.... can anyone give me any correct I/O? I failed to make some valid I/O for the 3rd case...

Posted: **Tue Nov 08, 2005 3:55 am**

arash_cordi wrote:
Code: Select all
char temp[100];

you should use temp[10000]...

but there is some other mistake.

Posted: **Sat May 05, 2007 9:32 pm**

Revenger wrote:Formula
Code: Select all
Ways[i,j]=Ways[i,j-1]+Ways[i-j,j]
is known by almost everybody (as I think). Although I wanted to use this formula in the contest, but I have a big problem: This formula only count the ways in which the biggest coin is equal to j; but how can I count the ways in which the number of coin is used. I have an idea about this, but this idea need a array[300][300][300] of 64-bit integers. So, it is not O(n^2) but O(n^3) and program need more than 32 MB of memory.
Can you give me a hint how to use this formula in more effective way?

Check out TopCoder problem "Computers". If you use the idea employed for that problem you can come up with the recurrence way[N][L] = way[N][L-1]+way[N-L][L]. It uses completely different diveration, but interesting comes out to be the same as coin change problems recurrence.

Posted: **Sat May 05, 2007 9:48 pm**

Oh....that's the same explaination as scythe's given.

Posted: **Sun Aug 10, 2008 5:21 pm**

by the recur A(i, j) = A(i, j-1) + A(i-j, j)
A(4,3) will be 3 because A(4,3) = A(4,2) + A(1,3)
= A(4,1) + A(2,2) + 0
= 1 + 1 = 2
but actually A(4,3) is only combination : {1,1,2}

am i wrong ??

or if i misunderstand the defination...cna someone help me, plz

Posted: **Mon Aug 11, 2008 5:21 pm**

If you are trying to get the value 4 with at most 3 coins, what you should call is A(4-3,3), which will give you A(1,3) = 1.

Posted: **Thu Jun 12, 2014 10:14 am**

ACTUALLY I HAVE READ THIS QUESTION AND CODE IT BUT SUDDENLY I REALIZE THAT THE LAST CONDITION ie N L1 L2 i am considering it wrognly ,please any one tell me what is the meaning of last conditon ,what i am doing is i am filling my coin array from l1 to l2 with increment by one and then use dynamic programming,
i am getting all answer correct but for the input N L1 L2 i am getting wrong answer,please help me!!

Posted: **Thu Jun 12, 2014 7:38 pm**

In the sample input 6 is the same as 6 1 6. For input N L1 L2 you can only use between L1 and L2 number of coins inclusive.

Posted: **Fri Jun 13, 2014 12:27 pm**

thanks but will you please tell me how many coins i can use for 100 10 10 input ,what is the range of coins?

Posted: **Fri Jun 13, 2014 6:06 pm**

For input 100 10 10 you can only use 10 coins, the output is 2977866.
For input 3 2 2, the output is 1: 1 + 2 = 3.

Posted: **Sat Jun 14, 2014 11:51 am**

one last question how you get the output 9 for input 6 2 5 ? i am asking this because i have spent so much time on this please tell about this test case

Posted: **Mon Jun 16, 2014 8:14 pm**

1 + 5
2 + 4
3 + 3
1 + 1 + 4
1 + 2 + 3
2 + 2 + 2
1 + 1 + 1 + 3
1 + 1 + 2 + 2
1 + 1 + 1 + 1 + 1

Posted: **Sun Mar 15, 2015 4:18 pm**

i just followed joe smith's suggestion and got ac

nice explanation

OJ Board

10313 - Pay the Price

10313

question

Re: 10313 - Pay the Price

problem no 10313

Re: problem no 10313

Re: problem no 10313

Re: problem no 10313

Re: problem no 10313

Re: problem no 10313

Re: 10313 - Pay the Price