My Weblog

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