## SPOJ 7897. Skyline

SPOJ 7897. Skyline is related to Catalan numbers.From wiki ” ** 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

No comments yet.

## Leave a Reply