X-Git-Url: https://git.njae.me.uk/?a=blobdiff_plain;f=app%2Fcses1620.hs;fp=app%2Fcses1620.hs;h=6d1b42ade8165c041b5879e99ab54fb98fdc5dfa;hb=dcd588a1259c400012f28c518bcc2e47abff9d61;hp=0000000000000000000000000000000000000000;hpb=02a7a583f2e54dab52af554dcb9831baa14fad38;p=cses-programming-tasks.git

diff --git a/app/cses1620.hs b/app/cses1620.hs
new file mode 100644
index 0000000..6d1b42a
--- /dev/null
+++ b/app/cses1620.hs
@@ -0,0 +1,41 @@
+import Data.List
+-- import Data.Ord
+import Data.Traversable
+import Control.Applicative
+
+
+main :: IO ()
+main = do
+  line1 <- getLine
+  line2 <- getLine
+  let params = map (read :: String -> Int) $ words line1
+  let required = params !! 1
+  let machines = map read $ words line2
+  -- print required
+  -- print machines
+  print $ solve required machines
+
+solve :: Int -> [Int] -> Int
+solve required machines
+  | required <= minProduction = minTime -- (required, minTime, minTime)
+  | otherwise = binarySearchTime required minTime maxTime machines
+  where minTime = minimum machines
+        minProduction = productionAtTime minTime machines
+        maxTime = findMaxTime required minTime machines
+
+findMaxTime :: Int -> Int -> [Int] -> Int
+findMaxTime required minTime machines
+  | required <= productionAtTime maxTime machines = maxTime
+  | otherwise = findMaxTime required maxTime machines
+  where maxTime = minTime * 2
+
+binarySearchTime required minTime maxTime machines
+  | minTime == maxTime = minTime
+  | midProduction < required = binarySearchTime required (midTime + 1) maxTime machines
+  | midProduction >= required = binarySearchTime required minTime midTime machines
+  where midTime = (minTime + maxTime) `div` 2
+        midProduction = productionAtTime midTime machines
+
+productionAtTime :: Int -> [Int] -> Int
+productionAtTime time machines = sum $ fmap go machines
+  where go machine = time `div` machine