![:(](./images/smilies/icon_frown.gif)
10313 - Pay the Price
Moderator: Board moderators
-
- New poster
- Posts: 6
- Joined: Fri Aug 06, 2004 10:00 am
- Location: (AIUB) Dhaka,Bangladesh
- Contact:
10313
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... ![:(](./images/smilies/icon_frown.gif)
![:(](./images/smilies/icon_frown.gif)
Programming Is An Art....You Have To Feel It...
you should use temp[10000]...arash_cordi wrote:Code: Select all
char temp[100];
but there is some other mistake.
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.Revenger wrote:Formulais 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.Code: Select all
Ways[i,j]=Ways[i,j-1]+Ways[i-j,j]
Can you give me a hint how to use this formula in more effective way?
question
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
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 ??
![:cry:](./images/smilies/icon_cry.gif)
electron
Re: 10313 - Pay the Price
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.
problem no 10313
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!!
i am getting all answer correct but for the input N L1 L2 i am getting wrong answer,please help me!!
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: problem no 10313
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.
Check input and AC output for thousands of problems on uDebug!
Re: problem no 10313
thanks but will you please tell me how many coins i can use for 100 10 10 input ,what is the range of coins? ![:)](./images/smilies/icon_smile.gif)
![:)](./images/smilies/icon_smile.gif)
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: problem no 10313
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.
For input 3 2 2, the output is 1: 1 + 2 = 3.
Check input and AC output for thousands of problems on uDebug!
Re: problem no 10313
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 ![:o](./images/smilies/icon_eek.gif)
![:o](./images/smilies/icon_eek.gif)
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: problem no 10313
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
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
Check input and AC output for thousands of problems on uDebug!
Re: 10313 - Pay the Price
i just followed joe smith's suggestion and got ac
nice explanation ![:)](./images/smilies/icon_smile.gif)
![:D](./images/smilies/icon_biggrin.gif)
![:)](./images/smilies/icon_smile.gif)