10313 - Pay the Price

[The CodeMaker (AIUB)]

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

[erictwpt]

Code: Select all

char temp[100];

you should use temp[10000]...

but there is some other mistake.

[yiuyuho]

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.

[yiuyuho]

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

[f74956227]

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

[yiuyuho]

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.

[so_whatt]

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!!

[brianfry713]

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.

[so_whatt]

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

[brianfry713]

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.

[so_whatt]

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

[brianfry713]

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

[anando_du]

i just followed joe smith's suggestion and got ac nice explanation