blob: ffbbdde52756ed193467505174ddd09f756e10c8 (
plain)
1
2
3
4
5
6
7
8
9
10
11
|
change [] n = if n == 0 then 1 else 0
change (x:xs) n = foldl (+) 0 $ map ((change xs).(n-)) avail
where avail = takeWhile (<=n) $ map (x*) [0..]
change' xs n = (foldl (flip $ (+).fst) 0).head.(drop n) $ [(1,0)]:changeIter [[(1,0)]]
where changeIter hist = h:(changeIter (h:hist))
where h = [ (foldl (+) 0 $ [m |(m,low)<-getH x,low<=x],x) |x<-xs]
getH x = let left=drop (x-1) hist in
if left/=[] then head left else []
main = putStrLn (show $ change' [25,10,5,1] 100000000)
|
