Google Code Jam Japan 2011 の予選Cの問題文が短かったのでやってみた。

やってみた。Haskellで。

import Control.Monad (forM_, liftM)
import Text.Printf (printf)
import Data.List (unfoldr)

f :: Integer -> Integer -> (Integer, Integer)
f 0 0 = (2, 1)
f 0 1 = (1, 0)
f 1 0 = (1, 1)
f 1 1 = (2, 1)

count :: Integer -> Integer -> Integer -> Integer
count s c 1 = s-c+1
count s c n = count (s+t) d q
    where (q,r) = divMod n 2
          (t,d) = f c r

-- output and input function
main :: IO ()
main = do [t] <- getList :: IO [Int]
          forM_ [1..t] $ \i -> do
            [n] <- getList :: IO [Integer]
            printf "Case #%d: %d\n" i $ count 0 0 n

getList :: Read a => IO [a]
getList = liftM (map read.words) getLine

予選の次がもう決勝なのね、今回は。