## SRM 524

Although i could not participate in the single round match 524 but i solved the division two problems in Haskell using gettc. For more detail , see the editorial .

module ShippingCubes where minimalCost :: Int -> Int minimalCost n = minimum [ i + j + k | i <- [ 1 .. n ] , j <- [ 1 .. n ] , k <- [ 1 .. n ] , i * j * k == n ]

module MagicDiamonds where prime :: [ Integer ] prime = 2 : 3 : filter isPrime [ 2 * k + 1 | k <- [ 1 .. ] ] isPrime :: Integer -> Bool isPrime n | n <= 1 = False | otherwise = all ( ( /= 0 ).mod n ) . takeWhile ( <= ( truncate . sqrt . fromIntegral $ n ) ) $ prime minimalTransfer :: Integer -> Integer minimalTransfer n | n == 3 = 3 | isPrime n = 2 | otherwise = 1

MultiplesWithLimit. For this problem , see the post of Smart.Coder.

module MultiplesWithLimit where import Data.List import qualified Data.Sequence as S import qualified Data.IntMap as M minMultiples :: Int -> [Int] -> String minMultiples n forbiddenDigits = format ret where lst = [ ( show i , mod i n ) | i <- [ 1 .. 9 ] , notElem i forbiddenDigits ] ; mp = M.fromList . zip ( map snd lst ) $ [ 1,1..] ret = helpMinMultiples ( S.fromList lst ) mp where helpMinMultiples t mp' | S.null t = "IMPOSSIBLE" | snd x == 0 = fst x | otherwise = helpMinMultiples xs'' mp'' where ( xs'' , mp'' ) = lookupfunction x xs mp' [ 0..9 ] forbiddenDigits n (x S.:< xs ) = S.viewl t lookupfunction :: ( String , Int ) -> S.Seq ( String , Int ) -> M.IntMap Int -> [ Int ] -> [ Int ] -> Int -> ( S.Seq ( String , Int ) , M.IntMap Int ) lookupfunction _ xs mp' [] _ _ = ( xs , mp' ) lookupfunction x xs mp' ( y : ys ) forbid n | elem y forbid = lookupfunction x xs mp' ys forbid n | otherwise = case M.lookup ( mod ( snd x * 10 + y ) n ) mp' of Nothing -> lookupfunction x ( xs S.|> ( fst x ++ show y , mod ( snd x * 10 + y ) n ) ) mp'' ys forbid n where mp'' = M.insert ( mod ( snd x * 10 + y ) n ) 1 mp' _ -> lookupfunction x xs mp' ys forbid n format :: String -> String format xs | xs == "IMPOSSIBLE" = "IMPOSSIBLE" | length xs < 9 = xs | otherwise = take 3 xs ++ "..." ++ drop ( len - 3 ) xs ++ "(" ++ show len ++" digits)" where len = length xs

Advertisements

For ‘isPrime’, you can also consider the sieve of eratosthenes:

primes = sieve [2..]

where sieve (x:xs) = x:(sieve (filter (ndivisp x) xs))

ndivisp denom num = mod num denom /= 0

Interestingly I believe your implementation – “filter through all possible divisors up to sqrt n” – is similar to what I do to try to figure out in my head if a number is prime – it is much more possible than trying to do a mental “sieve” approach!

Comment by gcbenison | November 25, 2011 |