Меню сайта

Категории раздела
Готовимся к олимпиаде по программированию (задачи взяты с сайта http://olimpiada.com.ru) [36]
Решение олимпиадных задач по программированию
Готовимся к олимпиаде по математике [3]
Решение олимпиадных задач по математике

Мини-чат

Наш опрос
Уважаемый посетитель сайта, к какой категории вы себя относите?
Всего ответов: 5512

Статистика

Онлайн всего: 1
Гостей: 1
Пользователей: 0


Главная

Регистрация

Вход
Вы вошли как Гость | Группа "Гости" | RSS


Личный сайт учителя математики и информатики

Фоновой Натальи Леонидовны



Пятница, 14.08.2020, 08:29
Главная » Файлы » Внеурочная деятельность » Готовимся к олимпиаде по программированию (задачи взяты с сайта http://olimpiada.com.ru)

Игра в города
13.02.2012, 19:32
Условие:
Всем известны правила игры "в города": первый игрок называет произвольный город, следующий - город, название которого начинается на ту же букву, на которую заканчивается название предыдущего города, и т.д. Аналогичным образом можно играть не в названия городов, а, например, в названия животных.
Задан список допустимых для описанной игры слов, слова в нём могут повторяться. Напишите программу, определяющую, в каком порядке в процессе игры должны быть названы слова из списка, чтобы каждое слово было использовано ровно столько раз, сколько оно в нём встречается.

Технические условия:
Во входном файле на первой строке записано число N - количество слов в списке (1<=N<=1000), а в последующих N строках - сами слова. Каждое из них является последовательностью не более, чем 10 строчных английских букв.
Выведите в выходной файл слова в исходном порядке, либо сообщение "NO", если такого порядка не существует. Каждое слово должно быть выведено в отдельную строку выходного файла.

Примеры входных и выходных файлов:
Input.txt
4
b
ab
bb
bb
Output.txt
ab
bb
bb
b

Решение:
by Алексей Ильичёв <alex_z77@mail.ru>

---------- cut ----------
Если построить граф, в котором буквы английского алфавита являются вершинами, а данные нам слова - рёбрами, то задача сведётся к построению Эйлерова пути в ориентированном графе.

Как изменится условие существования Эйлерова пути для ориентированного графа? Нетрудно понять, что для существования в ориентированном графе Эйлерова пути необходимо и достаточно, чтобы для каждой вершины кол-во входящих рёбер равнялось кол-ву выходящих, или для одной вершины кол-во входящих рёбер было больше на 1, а для другой кол-во выходящих было больше на 1.
При этом каждое ребро должно быть достижимым, то есть нет вершины, к которой подходит ребро и к которой нет пути из стартовой вершины.

Собственно алгоритм построения пути тот же самый, что и для неориентированного графа, за стартовую вершину принимается вершина, для которой кол-во выходящих рёбер на 1 больше.

PS. Если нужна дополнительная информация, такая например как теорема Эйлера с доказательством, или алгоритм построения Эйлерова пути - пишите.
---------- cut ----------

{$A+,B-,D+,E-,F-,G+,I-,L+,N+,O-,P-,Q-,R-,S-,T-,V+,X+,Y+}
{$M 16384,0,655360}

var
n, i, j : integer;
wrd : array[1..1000] of string[10]; {Тут храним слова}
rin, rout, {Кол-во входящих и выходящих рёбер}
hash : array[1..26] of integer; {указатель на элемент массива рёбер,
с которого начинаются рёбра, выходящие из данной вершины}
s, f : array[0..1000] of integer; {список рёбер - номера начальных и
конечных вершин}
sv, fv, {начальная и конечная вершины}
v : integer;
avail : array[1..26] of boolean; {существует ли путь из стартовой вершины
в данную}
way, ret : array[0..1000] of integer; {очередь рёбер}
deleted : array[1..1000] of boolean; {отмечаем уже использованные слова}
found : boolean;

procedure swap(i, j : integer);
var
st : string[10];
w : integer;
begin
w := s[i];
s[i] := s[j];
s[j] := w;
w := f[i];
f[i] := f[j];
f[j] := w;
st := wrd[i];
wrd[i] := wrd[j];
wrd[j] := st;
end;

procedure sort(l, r : integer);
var
x, i, j : integer;
begin
i := l;
j := r;
x := s[(l + r) div 2];
repeat
while s[i] < x do inc(i);
while s[j] > x do dec(j);
if i <= j then begin
swap(i, j);
inc(i);
dec(j);
end;
until i > j;
if i < r then sort(i, r);
if j > l then sort(l, j);
end;

procedure check(v : integer);
var
i : integer;
begin
avail[v] := true;
i := hash[v];
while (s[i] = v) do begin
if not avail[f[i]] then check(f[i]);
inc(i);
end;
end;

procedure movefrom(v : integer);
var
i : integer;
found : boolean;
begin
ret[0] := 0;
repeat
found := false;
i := hash[v];
while (s[i] = v) and (deleted[i]) do inc(i);
if s[i] = v then begin
found := true;
deleted[i] := true;
inc(ret[0]);
ret[ret[0]] := i;
v := f[i];
end;
until not found;
end;

begin
assign(input, 'input.txt');
reset(input);
readln(n);
for i := 1 to n do begin
readln(wrd[i]);
s[i] := ord(wrd[i, 1]) - ord('a') + 1;
f[i] := ord(wrd[i, length(wrd[i])]) - ord('a') + 1;
inc(rout[s[i]]);
inc(rin[f[i]]);
end; {читаем данные, считаем кол-во подходящих рёбер для каждой вершины}
close(input);
sort(1, n); {сортируем рёбра по начальной вершине}
for i := 1 to 26 do
if (rout[i] - rin[i] = 1) and (sv = 0) then sv := i
else if (rin[i] - rout[i] = 1) and (fv = 0) then fv := i
else if (rout[i] <> rin[i]) then begin
assign(output, 'output.txt');
rewrite(output);
writeln('NO');
close(output);
halt;
end; {Проверяем первое условие существования пути, записываем
стартовую и конечную вершины}
for i := 1 to n do if hash[s[i]] = 0 then hash[s[i]] := i; {формируем
массив указателей на элементы списка рёбер для каждой вершины}
if sv = 0 then for i := 1 to 26 do if rout[i] > 0 then sv := i; {если
стартовую вершину найти не удалось, берём произвольную}
check(sv); {обходом в глубину закрашиваем компоненту связности,
к которой относится первая вершина}
for i := 1 to 26 do if (not avail[i]) and (rin[i] > 0) then begin
assign(output, 'output.txt');
rewrite(output);
writeln('NO');
close(output);
halt;
end; {если не все рёбра достижимы, значит пути нет}
v := sv;
repeat
found := false;
i := hash[v];
while (s[i] = v) and deleted[i] do inc(i);
if s[i] = v then begin
found := true;
inc(way[0]);
way[way[0]] := i;
deleted[i] := true;
v := f[i];
end;
until not found; {идём от стартовой вершины, пока не упрёмся в конечную}
v := sv;
i := 0;
while i <= way[0] do begin
if rout[v] > 0 then begin
movefrom(v);
for j := way[0] downto i + 1 do way[j + ret[0]] := way[j];
inc(way[0], ret[0]);
move(ret[1], way[i+1], ret[0] shl 1);
end;
inc(i);
v := f[way[i]];
end; {добавляем к нашему пути все возможные циклы}
assign(output, 'output.txt');
rewrite(output);
for i := 1 to way[0] do writeln(wrd[way[i]]); {выводим ответ}
close(output);
end.
Категория: Готовимся к олимпиаде по программированию (задачи взяты с сайта http://olimpiada.com.ru) | Добавил: admin
Просмотров: 541 | Загрузок: 0 | Рейтинг: 0.0/0
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Форма входа

Поиск

Кнопка сайта

Одна кнопка

время жизни сайта

Сайт участвует
конкурс сайтов 

Новости образовани

Фраза дня

Web-мастеру

OperaFirefoxGoogle ChromeDownload Master
QIPSkypeµTorrentTeamViewer
Dr.Web CureITAvira AntiVirTotal CommanderCDBurnerXP
PicasaIrfanViewCheMaxDAEMON Tools
AIMPKMPlayerBSplayerK-Lite Codec Pack

Установить себе такой Блок
Скрипты и HTML для uCOz

Раскрутка сайта
Graffiti Decorations(R) Studio (TM) Site Promoter

Copyright MyCorp © 2020
/td>