ThemePark.hs

{-# OPTIONS_GHC -O2 -optc-O3 -optc-ffast-math -cpp #-}
{-# OPTIONS_GHC -funbox-strict-fields -fexcess-precision -monly-3-regs #-}
{-# LANGUAGE BangPatterns, OverloadedStrings, ScopedTypeVariables #-}
{-# LANGUAGE NoMonomorphismRestriction #-}
module Main where
import Control.Applicative
import Data.List
import Data.Function (on)
import Text.Printf
import Control.Monad
import Data.Tuple (swap)
import Data.Array


splitBy :: (a -> Bool) -> [a] -> [[a]]
splitBy p [] = []
splitBy p xs = a : (splitBy p $ dropWhile p $ b)
   where
     (a, b) = break p xs
 
split :: String -> [String]
split = splitBy (==' ')

toNum :: [[String]] -> [[Integer]]
toNum = (map $ map  ((+ 0) . read))
--input = lines <$> getContents
--input = lines <$> readFile "/Users/oskimura/prog/input.txt"
--input = lines <$> readFile "/Users/oskimura/Downloads/B-large-practice.in"
input = lines <$> readFile "/Users/oskimura/Downloads/C-large-practice.in"

interleave (x1:x2:xs) = (x1,x2) : interleave xs
interleave []         = []


f xs ys = take r . g $ ys'
    where 
      r = xs!!0
      k = xs!!1
      ys' = ys ++ ys'
      size = length ys
      g xs = s : (g xs')
          where
            ss = takeWhile (<=k) $ (scanl1 (+)  (take size xs))
            n = length ss
            s = last ss
            xs' = drop n xs

output xs = unlines . (zipWith (\ c n -> "Case #"++ show c ++": "++ show n) [1..]) $ xs
put = writeFile "output.txt"
main = do {count : nums <- map words <$> input
          ; put  . output . map sum . map (uncurry f). interleave . toNum $ nums 
          }