Google Code Jam Japan 2011 練習問題 問題A. 数珠繋ぎ

A-small-practice.hs

import Data.Char

splitBy :: (t -> Bool) -> [t] -> [[t]]
splitBy p [] = []
splitBy p xs = x : (splitBy p $ dropWhile p y)
    where (x, y) = break p xs

data State = ON | OFF deriving (Show, Eq)
toggle ON = OFF
toggle OFF = ON

next :: State -> [State] -> [State] -- 次の状態を生成する
next ON [] = []
next ON (x:xs) = toggle x : next x xs
next OFF xs = xs -- 通電していなければトグルしない

genNth :: [State] -> Int -> [State] -- N番目の状態を生成する
genNth xs 0 = xs
genNth xs n = genNth (next ON xs) $ n - 1

solve :: Int -> Int -> State    -- 地道に解く
solve' :: Int -> Int -> State   -- 効率良く解く

solve n k = if and . map (==ON) $ genNth (replicate n OFF) k then ON else OFF
solve' n k = if k `mod` (2^n) == 2^n-1 then ON else OFF

dispose :: Int -> Int -> IO () -- テストケースの数だけ解く
dispose 0 _ = return ()
dispose n m = do
    str <- getLine
    let n:k:_ = splitBy isSpace str in
        putStrLn $ "Case #" ++ show m ++ ": " ++ (show $ solve (read n :: Int) (read k :: Int))
    dispose (n - 1) (m + 1)

main = do
    n <- getLine
    dispose (read n :: Int) 1