10910 - Marks Distribution

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

Moderator: Board moderators

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Wed Jul 11, 2007 8:32 am

can anyone tell me what input will let it wrong
Try

Code: Select all

1
34 70 1
Correct output: 18204270


is it over flower for long long int ?
The first factorial that can't fit in a long long is 21! = 2^65.47...

lucky16g
New poster
Posts: 8
Joined: Sun Jul 01, 2007 7:25 pm

Post by lucky16g » Wed Jul 11, 2007 11:49 am

thanks to "mf" a lot

i have got ac

bonny
New poster
Posts: 3
Joined: Thu Aug 30, 2007 12:31 pm
Location: Dhaka

Re: 10910 - Marks Distribution

Post by bonny » Sun Dec 07, 2008 6:06 pm

It's simple, just like Binomial Showdown(530) :D

You have t-n*p extra marks, and you have to distribute them among n subjects. That means you have t-n*p marks, and you should put n-1 'separators' to divide them into n pieces. Imagine marks as 0's and separators as 1's. Now the problem is: How many different binary numbers can be formed with n-1 1's and t-n*p 0's ? The answer is (t-n*p+n-1)!/{(t-n*p)!(t-n*p)!), simply C(t-n*p+n-1, t-n*p), or C(t-n*p+n-1, n-1).

Just build a Pascal's triangle with 75 rows, then go! :D

P.S. Big integer may be needed.

Jehad Uddin
Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

Re: 10910 - Marks Distribution

Post by Jehad Uddin » Thu Sep 09, 2010 1:07 pm

Got WA only for big int
in the problem why this is given ??? :x
"You may assume that the final answer will fit in a standard 32-bit integer."

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: 10910 - Marks Distribution

Post by sohel » Fri Sep 10, 2010 9:26 am

As far as I remember, I got this problem AC without using bigint.

Jehad Uddin
Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

Re: 10910 - Marks Distribution

Post by Jehad Uddin » Fri Sep 10, 2010 1:33 pm

i got wa in this code,but when i switched to java ,in same process i got ac
this is the wa code

Code: Select all

code removed...
Last edited by Jehad Uddin on Mon Sep 13, 2010 10:13 am, edited 1 time in total.

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: 10910 - Marks Distribution

Post by sohel » Fri Sep 10, 2010 11:42 pm

I just submitted your code and it gets ACed.

Rashad
New poster
Posts: 17
Joined: Tue Dec 22, 2009 4:20 pm

Re: 10910 - Marks Distribution

Post by Rashad » Fri Sep 17, 2010 7:08 pm

"You may assume that the final answer will fit in a standard 32-bit integer." Is it true??!!

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: 10910 - Marks Distribution

Post by sohel » Fri Sep 17, 2010 11:44 pm

Yes, it is.

Rashad
New poster
Posts: 17
Joined: Tue Dec 22, 2009 4:20 pm

Re: 10910 - Marks Distribution

Post by Rashad » Sat Sep 18, 2010 6:12 pm

Yeah... Now I know that. Accepted!!! :wink:

Thanks for your reply.. :)

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re: 10910 - Marks Distribution

Post by DD » Sat Mar 26, 2011 6:58 pm

I use unsigned int to get accepted. Although my first A.C. solution set -1 to an unsigned int :oops: , it still get accepted :D
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

coder.tanvir
New poster
Posts: 11
Joined: Mon Mar 09, 2015 10:30 am

Re: 10910 - Marks Distribution

Post by coder.tanvir » Tue Jul 28, 2015 2:18 am

I have solved this problem using DP , but i cant figure out how it become Binomial coefficient.

Post Reply

Return to “Volume 109 (10900-10999)”