program optimaliree{ihput,outpui); coBst n --= il; [число ключей]

kin == .10; [максимальная длина ключа] type index = О.. и;

alfa = packed array [1., kin] of char; var ch: char;

kl, kl: integer;

id: alfa; {идентификатор или служебное слово] buf: шяу [1kin] ot char; [буфер символов] ~ key: array [1. .n] of alfa; i,i,k\ integer; a: array [1.. n] of integer; b: anay [index] of integer; p,w: япяу [index,index] of integer; FTarray [index,index] of index; suma, sumb: integer; tmctlonbaltree(i,j: index): integer;

var k: integer; begin к := (i+j+1) div 2; r[i,j] := k; it i >.J then baltree b[k] else

baltree := baliree(i,k-l) + baUree(Jc,j) + w[i,j] end [baltree] ; procedure opttree; уях x,nm: integer; i,j,k,h,m: index; begin [аргумент: w, результат: p, r]

for i 0 to и do p[i,i] :~ vf[iy]; {ширина дерева h = OJ for i := 0 to И-1 do {ширина дерева Л = 1)

begin у := i+l;

Р[1,П := Pim + pUJI; r[i,j] := J end ;

for A :== 2 to и do [Н-ширина текущего дерева]

for i := О to и-A do {i-левый индекс текущего дерева]

begin / := i+h; {j-правый индекс текущего дереея]

т := r[i,j-l]; min := p[i,m-l] + p[m,j]; for :== m+1 to do

begin X != р[/Л-Ц + P[k,j]; if л; < min then

begin m fc; тийг i- x end

end ;

:min + w[i,j]; r[i,j] ;= m

iisse printtree;

const /И' = 120; [размер строки АЦПУ) ref = ]node; linepositlon = 0 .. Iw; node - record Arej: alfa;

pos: linepositlon;

left, right, link: ref .

end ;

yssroot, current, next: ref; q,ql,g2: ref; i, k: integer;

u, гй, u2, u3, u4: linepositlon;

fttncfion tree(i,j: index): ref;

nrp: ref; \фа if i - J then := nil else

begin new(p);

pUeft := tree{i, гГ/,;]-!);

Ppos := trunc(,(lw-kln)*kl(n-l)) + (kin div 2); к :== +1; Pbkey := keylr[i,j]]; p\.right ;= tree{rli,jl J) end;

tree :~ p

Jia := 0; root := tree(0,n); mrrent := roof; root\.link := nil; Ш nil; while current Ф nil do

begin [продвижение вниз, сначала печать вертикальных строк] for i := 1 to 3 do begin и :~ 0; q := current; repeat ul := Qbpol

repeat write{ ); и 1= u+1 until M = wl;

writeCl); и :- и-rl; :=> gt- tintil g = nil; writeln end ;

[печать главной строки; сборка их потомков, спускаясь по узлам текущего спискаи формирование следующего списка]

current; и := 0; xepeatunpack(q\.key, buf, 1);

[центральный ключ] г := kin;

while бм/р] = do г i-l;

U2 := q.pos - ((i-1) div 2); мЗ := M2+i;

:= ql.left; ql := дТ- ЯА?; if q\ = nil then ul ul else

begin Ml := д1.;)05; ql.link := next; next := ql

end ;

if 2 = nil then м4 ;= иЗ else

begin u4 := 52t./)fl5+l; qlf.link := иел/; иш := 2 end ; i := 0;

while и < ul do begin writeC ); и := м+1 end ;

while и < ul do begin wnVe(-); м := u+l end ;

while и < u3 do begin i i+l; write(hif[i\);

while и < u4 do begin №г7е(-); м := м+1 end ;

g := qJink until g = nil; writeln;

[инвертирование следующего списка и превращение его в текущий] current := nil; while next Ф nil do

begin q -.- next; next := q\.link; q\.link := current; current := q

rend {printtree} ;

btgin [инициация таблицы ключей и счетчиков]