My Weblog

Blog about programming and math

SPOJ 7897. Skyline

SPOJ 7897. Skyline is related to Catalan numbers.From wiki ” C_n is the number of permutations of {1, …, n} that avoid the pattern 123 (or any of the other patterns of length 3); that is, the number of permutations with no three-term increasing subsequence”. Accepted Haskell code .

import Data.List
import Data.Ratio
import Control.Monad
import Data.Maybe
import qualified   Data.ByteString.Char8 as BS
import Data.Array

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

catlan :: [Integer]
catlan = 1 : zipWith (\c n ->  div ( c * 2 * ( 2 * n + 1 ) )   ( n + 2 )  ) catlan [1..]

catArray_1 ::  Array Int Integer
catArray_1  = listArray ( 0 , 1000 )  catlan

cat :: Array Integer Integer
cat = array (0,1000) ( [( 0 , 1 ) ] ++ [ ( i , div ( cat ! ( i - 1 ) *  ( 4 * i + 2 )  )  ( i + 2 )  ) | i <- [1..1000] ] )

solve :: Integer -> BS.ByteString
solve n = BS.pack.show $ mod ( cat ! ( n - 1 ) ) 1000000

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

Advertisements

July 11, 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: