Skip to content

@gorlum0 /Novice63.hs
Created

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
spoj - Novice63.hs
{-# 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]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.