My Weblog

Blog about programming and math

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 .

ShippingCubes .

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 ]

MagicDiamonds

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 Posted by | Programming | , , , , , | 1 Comment

   

Follow

Get every new post delivered to your Inbox.

Join 268 other followers