blob: cd11cd96521ec93d960470b32e36238dbfccc2cb (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
module Main where
import Data.List
import Data.Ord
import Input
import Util
main :: IO ()
main = do
inp <- map read . toList . splitOn (== ',') . head <$> getInput 7
let distfun1 x = sum [abs (x - p) | p <- inp] :: Int
distfun2 x = sum [let d = abs (x - p) in d * (d + 1) `div` 2 | p <- inp]
ternsearch lo hi f
| hi - lo <= 2 = minimumBy (comparing f) [lo, lo + (hi - lo) `div` 2, hi]
| otherwise =
let m1 = lo + (hi - lo) `div` 3
m2 = lo + 2 * (hi - lo) `div` 3
in if f m1 < f m2 then ternsearch lo m2 f else ternsearch m1 hi f
print (distfun1 $ ternsearch (minimum inp) (maximum inp) distfun1)
print (distfun2 $ ternsearch (minimum inp) (maximum inp) distfun2)
|
