My Weblog

Blog about programming and math

SPOJ 78. Marbles

SPOJ 78. Marbles is combinatorial problem. Lets say we have x_1 , x_2 ...x_k box in which we have to put n coloured marbles and each having at least one. Clearly  x_1 + x_2 + x_3 + ............. + x_k = n . The number of solution of this linear Diophantine equation , each of  x_1 , x_2 ..x_k positive, is {{n-1}\choose {r-1}} .

import Data.List


solve :: [Integer] -> String
solve (n:k:_) = show x where 
	a = min (k-1)  (n-k)
	b = max (k-1)  (n-k)
	x = div ( product [(n-1),(n-2)..(b+1)] ) ( product [1..a] )

main = interact $ unlines. map ( solve . map read . words ) . tail . lines
Advertisements

May 25, 2011 - Posted by | Programming | ,

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: