My Weblog

Blog about programming and math

SPOJ LQDCANDY

SPOJ LQDCANDY is almost similar to cut the silver bar except counting powers of 2 in length of candy. In this problem you have to find the next highest power 2 greater than n and how many times we need to break the candy each time half of the previous to get the length equal to n . Accepted Haskell code.

import Data.List
import Data.Bits
import qualified Data.ByteString.Char8 as BS 


solve::Integer -> BS.ByteString
solve n | (.&.) n (n-1) == 0 = BS.append ( BS.append ( BS.pack.show $ n ) ( BS.pack $ " " ) ) ( BS.pack.show $ 0 ) 
	| otherwise =  BS.append ( BS.append ( BS.pack.show $ a ) (BS.pack $ " " ) )  ( BS.pack.show.helpSolve a n $ 0 ) where 
		       b = until ( \x->2^x >= n ) (+1) 0 
     		       a = 2^b
		       helpSolve _ 0 cnt = (cnt-1)
		       helpSolve p k cnt = if p > k then helpSolve ( div p 2 ) k ( cnt + 1) else helpSolve ( div p 2 ) ( k - p ) ( cnt + 1) 

readInt :: BS.ByteString -> Integer
readInt x = case BS.readInteger x of
              Just ( i , _ ) -> i
	      Nothing -> error " upseperable ints "

main = BS.interact $ BS.unlines.map ( solve .readInt ) . tail.BS.lines
Advertisements

June 17, 2011 - Posted by | Programming | , ,

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: