Skip to content

Instantly share code, notes, and snippets.

@dfyz
Created January 29, 2013 19:45
Show Gist options
  • Save dfyz/4667106 to your computer and use it in GitHub Desktop.
Save dfyz/4667106 to your computer and use it in GitHub Desktop.
import Control.Applicative
import Control.Monad
import qualified Data.Map as M
import qualified Data.Set as S
import Data.Maybe
import Data.List
import Text.Printf
nextRng b c r prev = (b * prev + c) `mod` r
smartSolve :: TestCase -> Integer
smartSolve (TestCase n k a b c r) =
cyclingList !! (fromIntegral ((n - k - 1) `mod` (k + 1)))
where
startList = genericTake k (iterate (nextRng b c r) a)
positionMap = M.fromList $ filter ((<= k) . snd) $ zip [1..] startList
cyclingList = reverse $ snd $ mapAccumL getNumber (S.fromList [0..k]) [k, k-1..0]
getNumber availableNums pos =
let maxNum = S.findMax availableNums; next =
case M.lookup pos positionMap of
Just x -> if S.member x availableNums then x else maxNum
Nothing -> maxNum
in (S.delete next availableNums, next)
data TestCase =
TestCase Integer Integer Integer Integer Integer Integer
deriving Show
main = do
n <- readLn
forM_ [1..n] $ \i -> do
[n, k] <- readIntegers
[a, b, c, r] <- readIntegers
putStrLn ("Case #" ++ (show i) ++ ": " ++ (show $ smartSolve $ TestCase n k a b c r))
where
readIntegers = ((map read) . words) <$> getLine
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment