app/cses1620.hs

   1 import Data.List
   2 -- import Data.Ord
   3 import Data.Traversable
   4 import Control.Applicative
   5
   6
   7 main :: IO ()
   8 main = do
   9   line1 <- getLine
  10   line2 <- getLine
  11   let params = map (read :: String -> Int) $ words line1
  12   let required = params !! 1
  13   let machines = map read $ words line2
  14   -- print required
  15   -- print machines
  16   print $ solve required machines
  17
  18 solve :: Int -> [Int] -> Int
  19 solve required machines
  20   | required <= minProduction = minTime -- (required, minTime, minTime)
  21   | otherwise = binarySearchTime required minTime maxTime machines
  22   where minTime = minimum machines
  23         minProduction = productionAtTime minTime machines
  24         maxTime = findMaxTime required minTime machines
  25
  26 findMaxTime :: Int -> Int -> [Int] -> Int
  27 findMaxTime required minTime machines
  28   | required <= productionAtTime maxTime machines = maxTime
  29   | otherwise = findMaxTime required maxTime machines
  30   where maxTime = minTime * 2
  31
  32 binarySearchTime required minTime maxTime machines
  33   | minTime == maxTime = minTime
  34   | midProduction < required = binarySearchTime required (midTime + 1) maxTime machines
  35   | midProduction >= required = binarySearchTime required minTime midTime machines
  36   where midTime = (minTime + maxTime) `div` 2
  37         midProduction = productionAtTime midTime machines
  38
  39 productionAtTime :: Int -> [Int] -> Int
  40 productionAtTime time machines = sum $ fmap go machines
  41   where go machine = time `div` machine