# My Weblog

## 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 Data.Maybe
import qualified   Data.ByteString.Char8 as BS
import Data.Array

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

```