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 						

SPOJ 9948. Will it ever stop

SPOJ 9948. Will it ever stop is related to cycle detection. A simple and excellent problem to understand the cycle detection algorithm. Accepted Haskell code

import Data.List
import Data.Maybe
import qualified Data.ByteString.Lazy.Char8 as BS


solve :: Integer -> BS.ByteString
solve 1 =  BS.pack $ "TAK"
solve n = helpSolve n ( bCycle n ) where 
        helpSolve a b  
           | a == 1 || b == 1 =  BS.pack $ "TAK"
           | a == b =  BS.pack $ "NIE"
           | otherwise = helpSolve  ( bCycle a )  ( bCycle . bCycle $ b ) 

bCycle :: Integer -> Integer 
bCycle n 
  | even n = div n 2  
  | otherwise = 3 * n + 3 

reaD :: BS.ByteString -> Integer 
reaD = fst . fromJust . BS.readInteger 

main = BS.interact $   solve . reaD 

This solution is suggested by Hendrik.

import Data.Bits

reaD :: String -> Integer 
reaD = read 

main = interact $ (\n -> if  (.&.) n ( n - 1)== 0  then "TAK" else "NIE" ) . reaD 

Project Euler 357

Project Euler 357 is easy one. I was trying to solve problem 356 and finally ended up with solving easy problem. Nothing new just sieve of eratosthenes and couple of constraints.
Edit: Finally wrote a Haskell solution. See more discussion on Haskell-Cafe. Compile this code with ghc –make -O2 filename.hs

import Control.Monad.ST 
import Data.Array.ST 
import Data.Array.Unboxed 
import Control.Monad 
import Data.List


prime :: Int -> UArray Int Bool 
prime n = runSTUArray $ do 
    arr <- newArray ( 2 , n ) True :: ST s ( STUArray s Int Bool ) 
    forM_ ( takeWhile ( \x -> x*x <= n ) [ 2 .. n ] ) $ \i -> do 
        ai <- readArray arr i 
        when ( ai  ) $ forM_ [ i^2 , i^2 + i .. n ] $ \j -> do 
            writeArray arr j False 

    return arr 

pList :: UArray Int Bool 
pList = prime $  10 ^ 8 

divPrime :: Int -> Bool 
divPrime n = all ( \d -> if mod n d == 0 then pList ! ( d + div  n  d ) else True )  $  [ 1 .. truncate . sqrt . fromIntegral  $ n ] 



main = putStrLn . show . sum  $ ( [ if and [ pList ! i , divPrime . pred $ i ] then ( fromIntegral . pred $ i ) else 0 | i <- [ 2 .. 10 ^ 8 ] ] :: [ Integer ] ) 

#include<cstdio>
#include<iostream>
#include<vector>
#define Lim 100000001
using namespace std;

bool prime [Lim];
vector<int> v ;

void isPrime ()
     {
		for( int i = 2 ; i * i <= Lim ; i++) 
		 if ( !prime [i]) for ( int j = i * i ; j <= Lim ; j += i ) prime [j] = 1 ; 

		for( int i = 2 ; i <= Lim ; i++) if ( ! prime[i] ) v.push_back( i ) ;
		//cout<<v.size()<<endl;
		//for(int i=0;i<10;i++) cout<<v[i]<<" ";cout<<endl;

     }


int main()
	{
		isPrime();
		int n = v.size();
		long long sum = 0;
		for(int i = 0 ; i < n ; i ++) 
		 {
			int k = v[i]-1;
			bool f = 0;
			for(int i = 1 ; i*i<= k ; i++) 
				if ( k % i == 0 && prime[ i + ( k / i ) ] )  { f=1 ; break ; }
			
			if ( !f ) sum += k;
		 }
		cout<<sum<<endl;
	}