Меню сайта

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

Мини-чат

Наш опрос
Оцените мой сайт
Всего ответов: 2669

Статистика

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


Главная

Регистрация

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


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

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



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

Дерево
13.02.2012, 09:00
Условие:
Дерево из N вершин можно представить следующим образом: сначала все вершины нумеруются числами от 1 до N. Затем выкидывается лист с наименьшим номером и выписывается номер его предка. Такая операция повторяется до тех пор, пока не останется одна вершина. Врезультате получается последовательность из (n-1) числа. Требуется написать программу, которая по последовательности восстанавливает само дерево.

Технические условия:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени: 2 секунды на тест.

Входные данные:
Во входном файле на первой строке (N-1) (2<=N<=7500) число.

Выходные данные:
Выходной файл должен содержать N строк. В i-й строке должен быть список вершин, с которыми соеденина i-я вершина в порядке возрастания.

Примеры входных и выходных файлов:
Input.txt
1 1 6 2 6
Output.txt
3 4 6
5 6
1
1
2
1 2

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

---------- cut ----------
Идея решения. Анализируя алгоритм получения данной последовательности по дереву, нетрудно понять, что количество раз, которое номер вершины встречается в последовательности равняется степени вершины, уменьшенной на 1, то есть количеству потомков этой вершины. Зная степени вершин, нетрудно составить список всех листьев, и выбрав из них наименьший(то есть имеющий наименьший номер), можно установить к какой вершине он был подвешен. Далее эмулируем удаление этого листа, то есть
уменьшеем степень его предка на 1, если предок становится листом, добавляем его в очередь рассматриваемых листов. Всего эту операцию необходимо и достаточно повторить (n-1) раз, чтобы для каждой вершины (кроме имеющей максимальный номер) определить, к какой вершине она была подвешена.

В нашем случае важно быстро находить лист с наименьшим номером (см. ограничение по времени), поэтому имеет смысл построить приоритетную очередь для листьев. Вывод ответа тоже оптимизирован, чтобы хватило времени.
---------- cut ----------

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

var
list : array[1..7500] of integer; {Здесь храним исходную последовательность}
m : array[1..7500] of integer; {Степени вершин, уменьшенные на 1}
tree : array[1..7500] of integer; {Номера предков для всех вершин}
heap : array[0..7500] of integer; {Приоритетная очередь для листьев}
n, i, j : integer;
v : integer;
written : boolean;

procedure add(x : integer); {Процедура добавления элемента в очередь}
var
i, d : integer;
begin
inc(heap[0]);
i := heap[0];
d := i div 2;
while (d > 0) and (heap[d] > x) do begin
heap[i] := heap[d];
i := d;
d := i div 2;
end;
heap[i] := x;
end;

function min(i, j : integer) : integer; {Функция, возвращающая номер минимального элемента из i-го и j-го, j>i!}
begin
if (j > heap[0]) or (heap[i] < heap[j]) then min := i else min := j;
end;

function getfirst : integer; {Функция, возвращающая первый элемент очереди, и удалающая его из очереди}
var
i, d : integer;
x : integer;
begin
getfirst := heap[1];
x := heap[heap[0]];
dec(heap[0]);
i := 1;
d := min(2, 3);
while (d <= heap[0]) and (heap[d] < x) do begin
heap[i] := heap[d];
i := d;
d := min(i*2, i*2+1);
end;
heap[i] := x;
end;

begin
assign(input, 'input.txt');
reset(input);
while not seekeof do begin
inc(n);
read(list[n]);
inc(m[list[n]]);
end;
inc(n);
close(input);
for i := 1 to n do if m[i] = 0 then add(i);
for i := 1 to (n-1) do begin
tree[getfirst] := list[i]; {Записать номер предка}
dec(m[list[i]]); {Уменьшить степень предка}
if m[list[i]] = 0 then add(list[i]); {Если получили лист, добавить его в очередь}
end;
for i := 1 to (n-1) do inc(m[list[i]]); {Опять считаем степени вершин, это нам понадобится для оптимизации вывода ответа}
assign(output, 'output.txt');
rewrite(output);
for i := 1 to n do begin
v := tree[i];
if (v > 0) then written := false else written := true;
j := 0;
while m[i] > 0 do begin
inc(j);
if tree[j] = i then begin
if (v < j) and (not written) then begin
write(v, ' ');
written := true;
end;
write(j, ' ');
dec(m[i]);
end;
end;
if not written then write(v);
writeln;
end;close(output);end.
Категория: Готовимся к олимпиаде по программированию (задачи взяты с сайта http://olimpiada.com.ru) | Добавил: admin
Просмотров: 584 | Загрузок: 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>