Олимпиадная информатика - 2015

Задача « Очередь »

У кассы стадиона стоит длинная очередь из n человек. Как обычно, на время обеденного пе- рерыва кассу закрыли, и недовольная очередь футбольных фанатов разошлась по своим делам. Когда обед подходил к концу, все снова собрались у кассы. Ну и как же их теперь расставить в прежнем порядке? К счастью, все футбольные фанаты носили футболки с различными номерами на спине и каждый из них помнил номер на футболке стоявшего перед ним. Разумеется, кроме первого, стоявшего у кассы. Вам необходимо восстановить порядок стоявших в очереди фанатов.

Формат входного файла queue.in Входной файл: В первой строке записано одно целое число n - количество фанатов в очереди (2 <= n <= 2 * 1000000;). Следующие n - 1 строк содержат по два разделённых пробелом целых числа a и b - номера на футболках стоявших рядом друг с другом фанатов, где a - номер на футболке фаната, стоявшего за фанатом в футболке с номером b (1 <= a,b <= n).

Формат выходного файла queue.out Выходной файл: В единственной строке запишите через пробел n целых чисел - номера на футболках фанатов в обратном порядке очереди, начиная с последнего и заканчивая первым, стоявшим у кассы.

var 	a:array[0..2000002] of longint;
	q, p, n, k, i: longint;
begin
assign(input,'queue.in'); 
reset(input);
assign(output;'queue.out');
rewrite(output);
read(n);
k := 0;
for i:=1 to n - 1 do
begin
read(p, q);
a[p] := q;
k := k + i - q;
end;
k := k + n;
write(k);
for i := 1 to n - 1 do
begin
k := a[k];
write(' ', k);
end;
end.

close
 

Разбор задачи №1 "Очередь"

Запомним в массиве, кто за кем стоит. Элемент массива с индексом [i] равен номеру человека, который стоит непосредственно перед человеком с номером i. Последовательно выводим элементы массива: на очередном шаге выводим элемент массива с индексом, равным числу, выведенному непосредственно перед ним. Возникает вопрос, какое число вывести первым?

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