SPOJ SKYLINE

Link : SKYLINE

Category :Maths

Solution : Recurrence works out to be Catalan number.

Code:

	var cat:array[1..1001] of int64;
	var n:longint;
	const md:int64=1000000;
	procedure prep();
	var i,j:longint;
	var tmp:int64;
	begin
	cat[1]:=1;
	for i:=2 to 1001 do begin
	cat[i]:=0;
	for j:=1 to i-1 do begin
	tmp:=(cat[j]*cat[i-j]) mod md;
	cat[i]:=cat[i]+tmp;
	end;
	cat[i]:=cat[i] mod md;
	end;
	end;
	begin
	prep();
	while true do begin
	readln(n);
	if n=0 then break;
	writeln(cat[n+1]);
	end;
	end.

view raw skyline.pas hosted with ❤ by GitHub