Отправляет email-рассылки с помощью сервиса Sendsay

Олимпиадные задачи с решениями на Turbo Pascal

Подписаться Бесплатная «Золотая» новостная рассылка . Подписчиков 3.826 RSS
←   Ноябрь 2002   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


За последние 60 дней ни разу не выходила


Открыта: 02-12-2001

Автор
Aslof

Статистика

3.826 подписчиков
0 за неделю
←   Все выпуски   →

Олимпиадные задачи с решениями на Turbo Pascal


Информационный Канал Subscribe.Ru

Олимпиадные задачи с решениями на Turbo Pascal #34

Подписчиков на 2002-11-10 - 5107 человек(а).

Рассылка проекта "Олимпиада.com.ru".
Главная Архив задач Конкурс Обучение Рассылки Форум Контакты

Здравствуйте, уважаемые подписчики!
  Оргкомитет NetOI-2002 приглашает школьников Украины и других стран принять участие в открытой Всеукраинской олимпиаде по информатике с использованием сети Интернет.
  Подробности - на сервере http://www.olymp.vinnica.ua.

  В этом номере предлагаю вам ознакомиться с задачей, присланной мне Алексеем Ильичевым (за что ему огромное спасибо!).

ЗАДАЧИ

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

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

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

Output.txt
ab
bb
bb
b

Решение:

---------- 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.
Реклама в рассылке:

RLE    

  

Подпишитесь на наши рассылки:

Новости проекта "Олимпиада.com.ru" [Алексей Шамис]
Новости проекта "Olimpiada.com.ru". Новые темы на форуме. Информация о пополнениях в архиве задач. Оперативно и своевременно!

Уроки программирования на Turbo Pascal [Татьяна Ганилова]
Хотите стать Великим Программистом? Начните свой путь к вершине славы с изучения языка Turbo Pascal. Он как нельзя лучше подходит для начинающих программистов и в то же время используется для разработки сложных "профессиональных" программ.

 Олимпиадные задачи с решениями на Turbo Pascal [Алексей Шамис]
В рассылке публикуются решения интересных олимпиадных задач различного уровня. Содержит много теоретической информации. Периодичность - 2-3 раза в неделю.

 Задача в неделю. Олимпиадные задачи по информатике [Александр Алексеев]
Каждый понедельник в рассылке публикуется задача, которую необходимо решить и в следующий понедельник прислать программу на тестирование. Решения проверяются, и в пятницу публикуется разбор и итоги тестирования.

Всегда рады видеть Вас на нашем сайте.

Copyright © 2001-2002 by Aleksey Shamis.
http://subscribe.ru/
E-mail: ask@subscribe.ru 		Отписаться
Убрать рекламу
В избранное