The Haskell Program: A_balloons/balloons.hs
1
2
3
4 module Main where
5
6 import Text.Printf
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
17
18 showResults :: [ResultType] -> String
19 showResults = unlines . (map format)
20 format n = printf "%d" n
21
22
23
24
25
26
27
28 readTestCases :: String -> [InstanceType]
29 readTestCases = parse0 . (map read) . words
30
31
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
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
64
65
66