Done some puzzles

[cses-programming-tasks.git] / app / cses1620.hs

diff --git a/app/cses1620.hs b/app/cses1620.hs
new file mode 100644 (file)
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