Algorithm
Problem link- https://www.spoj.com/problems/SKYLINE/
SKYLINE - Skyline
The director of a new movie needs to create a scaled set for the movie. In the set there will be N skyscrapers, with distinct integer heights from 1 to N meters. The skyline will be determined by the sequence of the heights of the skyscrapers from left to right. It will be a permutation of the integers from 1 to N.
The director is extremely meticulous, so she wants to avoid a certain sloping pattern. She doesn’t want for there to be ANY three buildings in positions i, j and k, i < j < k, where the height of building i is smaller than that of building j, and building j’s height is smaller than building k’s height.
Your task is to tell the director, for a given number of buildings, how many distinct orderings for the skyline avoid the sloping pattern she doesn't like.
Input
There will be several test cases in the input. Each test case will consist of a single line containing a single integer N (3 ≤ N ≤ 1,000), which represents the number of skyscrapers. The heights of the skyscrapers are assumed to be 1, 2, 3, ..., N. The input will end with a line with a single 0.
Output
For each test case, output a single integer, representing the number of good skylines - those avoid the sloping pattern that the director dislikes - modulo 1,000,000. Print each integer on its own line with no spaces. Do not print any blank lines between answers.
Example
Input:
3
4
0
Output:
5
14
Code Examples
#1 Code Example with Python Programming
Code -
Python Programming
cat = [[0 for i in range(1005)] for j in range(1005)]
for i in range(1, 1005):
for j in range(i + 1):
if j == 0:
cat[i][j] = 1
else:
cat[i][j] = (cat[i][j - 1] + cat[i - 1][j]) % 1000000
while True:
N = int(input())
if N == 0:
break
print(cat[N][N])Input
4
0
Output
14
#2 Code Example with C++ Programming
Code -
C++ Programming
#include<stdio.h>
int arr[1005][1005]={{0}};
void catalan()
{
int i,j;
for(i=0;i<1005;i++)
{
for(j=0;j<=i;j++)
{
if(j==0)
arr[i][j]=1;
else
arr[i][j]=(arr[i][j-1]+arr[i-1][j])%1000000;
}
}
}
int main()
{
catalan();
int t;
scanf("%d",&t);
while(t)
{
printf("%d\n",arr[t][t]);
scanf("%d",&t);
}
return 0;
}Input
4
0
Output
14
Demonstration
SPOJ Solution-Skyline-Solution in C, C++, Java, Python