10313 - Pay the Price

All about problems in Volume 103. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

The CodeMaker (AIUB)
New poster
Posts: 6
Joined: Fri Aug 06, 2004 10:00 am
Location: (AIUB) Dhaka,Bangladesh
Contact:

10313

Post by The CodeMaker (AIUB) » 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... :(
Programming Is An Art....You Have To Feel It...

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

Post by erictwpt » 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.

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

Post by yiuyuho » 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.

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

Post by yiuyuho » Sat May 05, 2007 9:48 pm

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

Post by f74956227 » 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 ?? :cry: 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

Post by yiuyuho » 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.

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

problem no 10313

Post by so_whatt » 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!!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: problem no 10313

Post by brianfry713 » 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.
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

Post by so_whatt » 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? :)

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: problem no 10313

Post by brianfry713 » 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.
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

Post by so_whatt » 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 :o

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: problem no 10313

Post by brianfry713 » 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
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

Post by anando_du » Sun Mar 15, 2015 4:18 pm

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

Post Reply

Return to “Volume 103 (10300-10399)”