Широко известна игра «Города» (А.Н. Никитин). Называется какой-нибудь город, допустим, «Саратов». Кончается на «в», значит требуется назвать другой город, у которого в названии первая буква «в». Это может быть «Воронеж». Следующий город должен начинаться на «ж» и т.д. Запрещено повторять название городов. Надо написать программу, которая из набора названий городов (все названия разные) строит цепочку максимальной длины. Входные данные: файл TOWN.IN в 1-й строке содержит количество слов в наборе. Начиная со второй строки (по одному в строке) следуют названия городов (все буквы в названиях — заглавные).
Выходные данные: 1-я строка TOWN.OUT содержит длину максимальной цепочки. Начиная со второй строки идет вариант цепочки, т.е. названия (по одному в строке) городов в порядке, который требуют условия игры.
{$M $8000,0,$1FFFF}
program towns; { "Города". Решение А.Никитина, Самара }
const mnt = 20; { максимальное количество слов на входе }
var list,chain,store :array [1..mnt] of string; { для списка и цепочек }
numin :integer; { реальное количество слов на входе }
pc :integer; { Указатель на хвост цепочки }
ml :integer; { Длина наибольшей цепочки }
sym :char; { Первичная буква для перебора }
procedure read_data; { Начальные установки и чтение данных }
var i : integer;
begin
pc:=0; ml:=0; numin:=0;
assign(input,'TOWN.IN'); reset(input);
fillchar(chain,sizeof(chain),0);
readln(numin);
if (numin>mnt) then numin:=mnt;
for i:=1 to numin do readln(list[i]);
close(input);
end;
procedure write_results; { Запись результатов в файл }
var i : integer;
begin
assign(output,'TOWN.OUT'); rewrite(output);
writeln(ml);
if (ml>0) then begin
for i:=1 to ml do writeln(store[i]);
end;
close(output);
end;
procedure store_chain; { Запоминаем только более длинную цепочку }
var i:integer;
begin
if (pc>ml) then begin
store:=chain;
ml:=pc;
end;
end;
{ Возвращает указатель названия по 1-й букве, 0 - такого элемента нет }
function find_next_item( c:char; n:integer ):integer;
var i:integer;
begin
i:=1; find_next_item:=0;
while (i<=numin) and (n>0) do begin
if (list[i][1]=c) then dec(n);
inc(i);
end;
if (n=0) then find_next_item:=pred(i);
end;
{ Алгоритм построения цепочек. }
procedure build_chain( c:char; n:integer ); { Метод: перебор с возвратом. }
var i:integer; { Известен как "back-tracking" }
begin
i:=find_next_item(c,n);
if (i>0) then begin
inc(pc); chain[pc]:=list[i]; list[i][1]:='X'; { вычеркиваем }
build_chain(list[i][length(list[i])], 1);
dec(pc); list[i][1]:=c; { возвращаем }
build_chain(c, n+1);
end else store_chain;
end;
begin
read_data;
for sym:='А' to 'Я' do build_chain(sym,1);
write_results;
end.