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


import qualified Data.Map
--import Control.Monad.State


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 :: Num a => [[String]] -> [[a]]
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@[r,k,n] ys = g arr r
    where arr = phi k $ ys
     
phi :: Integer -> [Integer] -> ST
phi k xs = listArray (0,(genericLength arr)-1) arr
         where 
           n         = (genericLength xs)
           less j qs =  last . zipWith (\a b -> (a `mod` n ,b)) [j+1..] $ (map fst . takeWhile ((<=k) . fst) . zip (scanl1 (+) qs) $ qs) 
               -- +1 is next 
           arr = zipWith less [0..] $ [take n . drop i $ (xs++xs)  | i <- [0..n-1]]



type ST = Array Integer (Integer, Integer)

g :: ST -> Integer -> Integer
g a n = snd . (!0) . z n $ a
    where
      z n arr
          | n==0         = zero
          | n==1         = arr
          | n `mod` 2==0 = arr2 `add` arr2
          | otherwise    = arr2 `add` arr2 `add` arr  -- let m' = comb . comb $ m in comb m'
              where
                arr2    = z (n `div` 2) arr 
                zero = listArray (1,n) [(i,0) | i<-[1..n]]
      comb:: (Integer,Integer) -> (Integer,Integer)
      comb (i1,c1) = (i2,c2+c1)
          where (i2,c2) = a!(i1)

add :: ST -> ST -> ST
add a1 a2 = listArray t [ (i2,c1+c2) | i <- range t
                        , let (i1,c1) = a1!i
                        , let (i2,c2) = a2!i1]
    where t = bounds a1

phi' xs = [take n . drop i $ (xs++xs)  | i <- [0..n]]
    where n    = length xs

less k qs =  last . zip (map fst . takeWhile ((<=k) . fst) . zip (scanl1 (+) qs) $ qs) $ [1..n]
    where  n = genericLength qs



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 (uncurry f) . interleave . toNum $ nums 
          }