# 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

## SRM 385 – Division II, Level Three

Gettc is excellent software for practicing topcoder problems offline and specially in Haskell. I just wrote solution for SRM 385 Problem [ requires registration but its worth and excellent place for programmers ]. You can see the editorial for SRM 385. Haskell source code.

```module SummingArithmeticProgressions where

canRep :: Int -> Int -> Int -> Bool
canRep a b n = canRephelp 1 a b n where
canRephelp x a b n
| x > b = False
| n <= a * x = False
| mod ( n - a * x ) b == 0 = True
| otherwise = canRephelp  ( succ x ) a b n

howMany :: Int -> Int -> Int -> Int
howMany left right k =  ans   where
a = k
b = div ( k * ( k - 1 ) ) 2
d = gcd a b
a' = div a d
b' = div b d
left' = div ( left + d - 1 ) d
right' = div right d
ans = helphowMany a' b' left' right'  0

helphowMany :: Int -> Int -> Int -> Int -> Int -> Int
helphowMany a b left right cnt
| and [ left <= right , left < 2 * a * b ] = if canRep a b left
then helphowMany a b ( succ left ) right ( succ cnt )
else helphowMany a b ( succ left ) right cnt
| otherwise = cnt + right - left + 1
```

September 7, 2011 Posted by | Programming | , , | 1 Comment