The Haskell Program: A_balloons/balloons.hs

  1 -- SER 2010.  Problem A: Balloons
  2 -- Author: Ryan Stansifer
  3 
  4 module Main where
  5 
  6 import Text.Printf         -- import text formating function
  7 import Data.List (sortBy)
  8 
  9 main :: IO()
 10 main = interact (showResults . map total . readTestCases)
 11 
 12 type InstanceType = (Int,Int,[(Int,Int,Int)])
 13 type ResultType = Int
 14 
 15 --
 16 -- Show the results of all the test cases
 17 --
 18 showResults :: [ResultType] -> String
 19 showResults = unlines . (map format)
 20 format n = printf "%d" n
 21 
 22 
 23 --
 24 -- Format the results of all the test cases
 25 --
 26 
 27 -- Break the entire input up into individual integers
 28 readTestCases :: String -> [InstanceType]
 29 readTestCases = parse0 . (map read) . words
 30 
 31 -- Break the input up into a list of individual test cases
 32 parse0 :: [Int] -> [InstanceType]
 33 parse0 (0:rest) = []
 34 parse0 (n:a:b:rest)  = parse1 (n,a,b) rest
 35 
 36 parse1 :: (Int,Int,Int)-> [Int] -> [InstanceType]
 37 parse1 (n,a,b) rest = (a,b,(triples (take (3*n) rest) [])) : (parse0 (drop (3*n) rest))
 38 
 39 triples :: [Int] -> [(Int,Int,Int)] -> [(Int,Int,Int)]
 40 triples [] acc = acc
 41 triples (x:y:z:rest) acc = triples rest ((x,y,z):acc)
 42 
 43 --
 44 -- Solve the problem for one test case
 45 --
 46 total :: InstanceType -> ResultType
 47 total (a,b,ts) = let (_,_,d) = foldr totalTeam (a,b,0) (sortBy absDiff ts) in d
 48 
 49 absDiff (_,d1,d2) (_,d1',d2') = compare (abs (d1-d2)) (abs (d1'-d2')) 
 50 
 51 preferA (_,d1,d2) = d1<d2
 52 preferB (_,d1,d2) = not (d1<d2)
 53 
 54 totalTeam t@(n,d1,d2) state@(a,b,d)
 55   | n > a+b = error "not enough"
 56   | preferA t = let (a',b')=subA a b n in (a-a',b-b',d+a'*d1+b'*d2)
 57   | preferB t = let (a',b')=subB a b n in (a-a',b-b',d+a'*d1+b'*d2)
 58   | otherwise = error "impossible"
 59   
 60 subA a b n = if (a>n) then (n,0) else (a,n-a)
 61 subB a b n = if (b>n) then (0,n) else (n-b,b)
 62 
 63 --  ------------For GNU Emacs ------------
 64 --  Local Variables:
 65 --  compile-command: "ghc --make balloons"
 66 --  End: