public
Created

spoj - Novice63.hs

  • Download Gist
Novice63.hs
Haskell
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
{-# OPTIONS_GHC -O2 -XNoMonomorphismRestriction #-}
{-# LANGUAGE BangPatterns #-}
{-(c) gorlum0 [at] gmail.com-}
import qualified Data.ByteString.Char8 as BS
import Data.Maybe (fromJust)
 
readNum = fst . fromJust . BS.readInteger
fI = fromIntegral
 
fact n = product [1..n]
binom n k = (fact n) `div` (fact k) `div` (fact $ n - k)
 
-- only evens - 0 for odds
specials = [if even n then binom (n-1) k else 0 |
n <- [1,2..60], let k = n`div`2 - 1]
 
totalSpecials :: Integer -> Integer
totalSpecials 2 = 1
totalSpecials n = sum $ take m specials
where m = floor $ logBase 2 (fI n)
 
main = do
(l:ls) <- BS.lines `fmap` BS.getContents
let t = readNum l
ns = map readNum ls
mapM_ print [totalSpecials n | n <- ns]

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.