# My Weblog

## 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
```

November 22, 2011 -

## 1 Comment »

1. 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 | Reply