app/cses1620_slow.hs

   1 import Data.List
   2 -- import Data.Ord
   3 import Data.Traversable
   4 import Control.Applicative
   5
   6 type MergedMachine = (Int, Int) -- production time, number of machines
   7
   8
   9 main :: IO ()
  10 main = do
  11   line1 <- getLine
  12   line2 <- getLine
  13   let params = map (read :: String -> Int) $ words line1
  14   let required = params !! 1
  15   let machines = map read $ words line2
  16   let mergedMachines = merge machines
  17   -- print required
  18   -- print machines
  19   print  mergedMachines
  20   print $ length mergedMachines
  21   print $ solve required mergedMachines
  22
  23 merge :: [Int] -> [MergedMachine]
  24 merge machines = [(head g, length g) | g <- grouped_machines]
  25   where sorted_machines = sort machines
  26         grouped_machines = group sorted_machines
  27
  28
  29 -- solve :: Int -> [Int] -> Int
  30 solve required ms = (lcm_chunks * lcm_time) + length requiredRun - 1
  31   -- lcm_production
  32   where lcm_time = lcms $ fmap fst ms
  33         lcm_production = sum $ [(lcm_time `div` p) * n | (p, n) <- ms]
  34         lcm_chunks = required `div` lcm_production
  35         remaining = required `mod` lcm_production
  36         prods = productions ms
  37         -- requiredRun = takeWhile (< required) $ totalProductions prods
  38         requiredRun = takeUntil (>= remaining) $ totalProductions prods
  39         -- sorted_ms = sortOn Down ms
  40
  41 lcms :: [Int] -> Int
  42 lcms ns = foldl1 lcm ns
  43
  44 productions :: [MergedMachine] -> [[Int]]
  45 productions machines = fmap manufactured machines
  46
  47 manufactured :: MergedMachine -> [Int]
  48 manufactured (t, n) = go [0, n..]
  49   where go (p:ps) = replicate t p ++ go ps
  50
  51 totalProductions :: [[Int]] -> [Int]
  52 totalProductions prods = fmap sum $ getZipList $ sequenceA $ fmap ZipList prods
  53
  54 takeUntil _ [] = []
  55 takeUntil p (x:xs)
  56   | p x = [x]
  57   | otherwise = x : takeUntil p xs