CCandyplitting.hs

{-# OPTIONS_GHC -O2 -optc-O3 -optc-ffast-math -cpp #-}
module Main where
import Data.List 
import Control.Monad
import Data.Array 
import Control.Applicative
import Text.Printf
import Data.Bits

divid :: [Int] -> [([Int], [Int])]
divid xs = zip (map sort . inits $ xs) (map sort . tails $ xs)


notE = filter (not . null)

check x y = (adds x) == (adds y)
 
badd b1 b2 = b1 `xor` b2

adds :: [Int] -> Int
adds xs = foldr badd 0 xs


solve xs =  if null as then "NO" else show . maximum . concat . map phi $ as
    where
      as = concat $ [ [ zs  | zs <- concat . map divid  . permutations $ xs
                      , notE' zs ,(uncurry check) zs
                      ] 
                    ] 

      notE' (f,s) = (not . null $ f) && (not . null $ s)
      phi (f,s)   = [sum f , sum s]

solve' xs = listArray

rr :: String -> Int
rr = read

main =  do { t <- rr <$> getLine
           ; forM_ [1..t] (\ i -> do  { n <- rr <$> getLine
                                      ; cs <- (map rr) . words <$> getLine
                                      ; printf "%s\n" $ ("Case #" ++ show i ++ ": " ++ (solve . sort $ cs))
                                      })
           }