## 10313 - Pay the Price

Moderator: Board moderators

The CodeMaker (AIUB)
New poster
Posts: 6
Joined: Fri Aug 06, 2004 10:00 am
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...
Programming Is An Art....You Have To Feel It...

erictwpt
New poster
Posts: 6
Joined: Mon Oct 10, 2005 5:13 am
Location: Taiwan
arash_cordi wrote:

Code: Select all

``char temp[100];``
you should use temp[10000]...

but there is some other mistake.

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
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.

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
Oh....that's the same explaination as scythe's given.

f74956227
New poster
Posts: 37
Joined: Sun Jan 27, 2008 1:50 am
Location: Taiwan
Contact:

### 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
electron

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

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

so_whatt
New poster
Posts: 3
Joined: Thu Jun 12, 2014 10:09 am

### 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,

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

so_whatt
New poster
Posts: 3
Joined: Thu Jun 12, 2014 10:09 am

### 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?

brianfry713
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.
Check input and AC output for thousands of problems on uDebug!

so_whatt
New poster
Posts: 3
Joined: Thu Jun 12, 2014 10:09 am

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

brianfry713
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
Check input and AC output for thousands of problems on uDebug!

anando_du
New poster
Posts: 10
Joined: Sun Mar 01, 2015 3:11 pm

### Re: 10313 - Pay the Price

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