mon@razerRamon:~/tmp/ncpc17$ ll
total 109M
drwxrwxr-x  3 mon mon 4.0K Oct 14 16:42 assets/
drwxrwxr-x 13 mon mon 4.0K Oct 14 12:34 ncpc2017-testdata/
-rwxrwxr-x  1 mon mon  257 Oct 14 16:19 BestRelayTeam.bash*
-rwxrwxr-x  1 mon mon 4.0K Oct 14 16:23 BestRelayTeam.hs*
-rw-rw-r--  1 mon mon  699 Oct 14 16:24 BestRelayTeam.sample.output
-rw-rw-r--  1 mon mon 138K Oct 14 16:24 BestRelayTeam.secret.output
-rw-rw-r--  1 mon mon  59K Oct  7 12:19 Language Haskell - Kattis, The 2017 Nordic Collegiate Programming Contest.pdf
-rw-rw-r--  1 mon mon 4.7M Oct  7 12:29 ncpc2017problems.pdf
-rw-rw-r--  1 mon mon 104M Oct 11 09:00 ncpc2017-testdata.tar.bz2
-rwxrwxr-x  1 mon mon 1.2K Oct 14 14:00 ScriptTemplate.hs*
-rw-rw-r--  1 mon mon    8 Oct  7 12:42 ScriptTemplate.input
mon@razerRamon:~/tmp/ncpc17$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#!/usr/bin/env stack
{- stack
   --resolver ghc-7.10.3
   --install-ghc
   runghc
   --
   -rtsopts -ferror-spans
   +RTS -M1024m -K8m -RTS
-}

{-
  * GHC used by NCPC:
      The Glorious Glasgow Haskell Compilation System version 7.10.3

  * Flags required by NCPC:
      -O2 -threaded -rtsopts -ferror-spans
      +RTS -M{memlim}m -K8m -RTS

  ... but, due to warnings (ignored), some are removed: 
      when making flags consistent: Warning:
          -O conflicts with --interactive; -O ignored.
      Warning: -debug, -threaded and -ticky are ignored by GHCi

  * Flags in order to make optimal code (exhaustive):
      -Wall -Werror

  ... but if used, it would require way more code (time is mana)
-}

module Main (main) where

data Runner = Runner
  { surname :: String
  , fstleg  :: Double
  , sndleg  :: Double
  }

data Runners = Runners
  { number   ::  Int
  , athletes :: [Runner]
  }

data RelayTeam = RelayTeam
  { time   :: Double
  , first  :: Runner
  , second :: Runner
  , third  :: Runner
  , fourth :: Runner
  }

instance Eq Runner where
  Runner name1 fstleg1 sndleg1 == Runner name2 fstleg2 sndleg2 =
    name1 == name2 && fstleg1 == fstleg2 && sndleg1 == sndleg2
  Runner name1 fstleg1 sndleg1 /= Runner name2 fstleg2 sndleg2 =
    name1 /= name2 || fstleg1 /= fstleg2 || sndleg1 /= sndleg2

instance Read Runner where
  readsPrec _ input =
    let
      aux [        ] = []
      aux (name:fstleg:sndleg:[]) =
        [(Runner name (read fstleg) (read sndleg), "")]
      aux [   _    ] = []
    in
      aux $ words input

instance Read Runners where
  readsPrec _ input =
    let
      aux [    ] = []
      aux (x:xs) =
        let
          nr = read x
        in
          [(Runners nr (aux' nr xs), "")]
      aux' 0 [    ] = [                        ]
      aux' n (x:xs) = (read x) : aux' (n-1) xs
    in
      aux $ lines input

instance Show Runner where
  show (Runner surname _ _) = surname

instance Show RelayTeam where
  show (RelayTeam time first second third fourth) =
    show time   ++ "\n" ++
    show first  ++ "\n" ++
    show second ++ "\n" ++
    show third  ++ "\n" ++
    show fourth ++ "\n"

nrdec :: Double -> Int -> Double
nrdec x n =
  fromIntegral (round $ x * z) / z
  where z = 10 ^ n
  
solve :: Runners -> RelayTeam
solve (Runners _ xs) =
  let
    dummy = Runner "DUMMY" 9999.99 9999.99
    init  = (dummy,dummy,dummy,dummy)
    
    ftime (Runner _ t _) = t
    stime (Runner _ _ t) = t
    bstime (a,b,c,d) (w,x,y,z) =
      stime a + stime b + stime c + stime d <
      stime w + stime x + stime y + stime z
    bctime (a,b,c,d) (w,x,y,z) =
      ftime a + stime b + stime c + stime d <
      ftime w + stime x + stime y + stime z

    aux (a,b,c,d) _ [    ] =
      RelayTeam (nrdec (ftime a + stime b + stime c + stime d) 2) a b c d
    aux acc (a,b,c,d) (y:ys) =
      {- Linear time with only 8 extra memory usage -}
      let
        abcd =
          if a == y then
            (y,b,c,d)
          else
            if b == y then
              (y,a,c,d)
            else
              if c == y then
                (y,a,b,d)
              else
                (y,a,b,c)
      in
        if bctime abcd acc then 
          aux abcd (a,b,c,d) ys
        else
          aux acc  (a,b,c,d) ys
      
    aux' (a,b,c,d) [    ] = (a,b,c,d)
    aux' (a,b,c,d) (y:ys) =
      {- Linear time with only 4 extra memory usage -}
      if bstime (y,b,c,d) (a,b,c,d) then
        aux' (y,b,c,d) (a:ys)
        else
        if bstime (a,y,c,d) (a,b,c,d) then
          aux' (a,y,c,d) (b:ys)
        else
          if bstime (a,b,y,d) (a,b,c,d) then
            aux' (a,b,y,d) (c:ys)
          else
            if bstime (a,b,c,y) (a,b,c,d) then
              aux' (a,b,c,y) (d:ys)
            else
              aux' (a,b,c,d) ys
  in
    aux init (aux' init xs) xs

readInput :: String -> Runners
readInput =
  read

writeOutput :: RelayTeam -> String
writeOutput =
  show

main :: IO ()
main =
  interact $ writeOutput . solve . readInput

#!/bin/bash

for f in $1*.in; do
    echo " "
    echo "- "$f
    cat $f
    echo "- "${f%.*}.ans
    cat ${f%.*}.ans
    echo "- result:"
    cat $f | ./BestRelayTeam.hs
    echo "- diff:"
    cat $f | ./BestRelayTeam.hs | diff - ${f%.*}.ans
done

./BestRelayTeam.bash ncpc2017-testdata/bestrelayteam/sample/

 
- ncpc2017-testdata/bestrelayteam/sample/1.in
6
ASHMEADE 9.90 8.85
BLAKE 9.69 8.72
BOLT 9.58 8.43
CARTER 9.78 8.93
FRATER 9.88 8.92
POWELL 9.72 8.61
- ncpc2017-testdata/bestrelayteam/sample/1.ans
35.54
CARTER
BOLT
POWELL
BLAKE
- result:
35.54
CARTER
BOLT
POWELL
BLAKE
- diff:
 
- ncpc2017-testdata/bestrelayteam/sample/2.in
9
AUSTRIN 15.60 14.92
DRANGE 15.14 14.19
DREGI 15.00 14.99
LAAKSONEN 16.39 14.97
LUNDSTROM 15.83 15.35
MARDELL 13.36 13.20
POLACEK 13.05 12.55
SANNEMO 15.23 14.74
SODERMAN 13.99 12.57
- ncpc2017-testdata/bestrelayteam/sample/2.ans
52.670000
MARDELL
POLACEK
SODERMAN
DRANGE
- result:
52.67
MARDELL
POLACEK
SODERMAN
DRANGE
- diff:
1c1
< 52.67
---
> 52.670000

./BestRelayTeam.bash ncpc2017-testdata/bestrelayteam/secret/

- ncpc2017-testdata/bestrelayteam/secret/01-crazy.in
10
QXBINSJS 10.91 8.16
WKN 18.65 15.09
CPP 16.38 9.38
KDNLKJMYIWFSGYWY 12.53 11.18
KXS 19.64 13.63
OYCJANFTSGQTZMIJD 16.16 8.32
ZKGNNS 17.32 16.16
LDOYLWRXVXAJEVDOWXNF 13.02 12.58
IVONUZJE 11.52 10.37
KMEVNRHQSQPUYEYBP 18.71 9.63
- ncpc2017-testdata/bestrelayteam/secret/01-crazy.ans
37.38
IVONUZJE
QXBINSJS
OYCJANFTSGQTZMIJD
CPP
- result:
37.38
IVONUZJE
QXBINSJS
OYCJANFTSGQTZMIJD
CPP
- diff:
 
- ncpc2017-testdata/bestrelayteam/secret/02-crazy.in
50

...

- ncpc2017-testdata/bestrelayteam/secret/15-sequential.ans
60.06
GGURGO
NXZUEOA
BOHPBXMYSTFJUPUA
IOYBAEDMKSKO
- result:
60.06
IOYBAEDMKSKO
GGURGO
NXZUEOA
BOHPBXMYSTFJUPUA
- diff:
2d1
< IOYBAEDMKSKO
5a5
> IOYBAEDMKSKO

...

- ncpc2017-testdata/bestrelayteam/secret/30-sequential-secondbest-firstpart.ans
51.99
SECONDBEST
BEST
JMBCIRVTIHVRKRZZTXSD
RJZMGLUWHOJBLQGIUWZD
- result:
51.99
SECONDBEST
BEST
JMBCIRVTIHVRKRZZTXSD
QQYBKUPSWYKJCUODUSMA
- diff:
5c5
< QQYBKUPSWYKJCUODUSMA
---
> RJZMGLUWHOJBLQGIUWZD