OIM地形
二维离散世界有一种地形叫OIM(OI Mountain)。这种山的坡度只能上升('/')或下降('\'),而且两边的山脚都与地平线等高,山上所有地方都不低于地平线。例如:
/\ /\
/ \/\ 是一座OIM:而/ \ 不是。
\/
这个世界的地理学家们为了方便记录,给OIM所有可能的形状用正整数编好号,而且每个正整数恰好对应一种山形。他们规定,若两座山的宽度不同,则较宽的编号较大;若宽度相同,则比较从左边开始第1个坡度不同的地方,坡度上升的编号较大。以下三座OIM的编号由小到大递增:
/\ /\ /\ /\
/ \/\ / \/\/\ / \/ \。显然/\的编号为1。但是地理学家在整理记录时发觉,查找编号与山形的对应关系不是很方便。他们希望能快速地从编号得到山的形状。你自告奋勇答应给他们写一个程序,输入编号,能马上输出山形。
输 入:
一个编号(编号大小不超过600,000,000),
输 出:
输入编号所对应的山形,l座山所占行数恰为它的高度,即山顶上不能有多余空行。
输入样例:
15
输出样例:
/\ /\
/ \/ \
程 序:
program Programg2;
const
L :integer=19; SZ :integer=50;
Up :char='/';DN :char'\';
Var
i,nth,x,y,h,e,f:integer;
m :array[0..1,0..38,0..19]0f integer;
pic:array[0..49,0..49]of char;
procedure init;
var k,s,a,b,c:integer;
begin
for a := 0 to 1 do
for b :=0 to 2*L do
for c:=0 to L do
m[a,b,c]:=0; m[0,0,0]:=1;
for k:=0 to 2*L-1 do
begin
for s:=1 to L do
begin
m[0,k+1,s]:=m[0,k,s+1]+m[1,k,s+1];
m[1,k+1,s]:= m[0,k,s-1]+m[1,k,s-1] ;
end;
m[0,k+1,0]:=m[0,k,1]+m[1,k,1];
end;
end:
procedure draw(k,s,nth: integer);
begin
if(k=0) then exit;
if ((nth-m[1,k,s])>=0)then
begin
nth:= nth-m[1,k,s];
if (y>h) then h:=y ;
pic[y,x]:= UP; y:=y+1;x:=x+l; draw( k-1,s+1,nth );
end
else begin
y:=y-1; pic[y,x]:=DN; x:=x+1; draw(k-1,s-l,nth);
end;
end:
begin
init;
read(nth);
for e:= 0 to SZ-1 do
for f:=0 to SZ-l do
pic[e,f]:=' ';
x:=0;
y:=0;
h:=0;
i:=0;
while((nth-m[0,2*i,0])>=0)do
begin
nth:=nth-m[0,2*i,0];
i:=i+1 ;
end;
draw( 2*i,0,nth );
for i := h downto 0 do
begin
for e :=0 to x-1 do
write(pic[i,e]);
writeln(' ');
end;
end.