Олимпиадные задачи по программированию со "спрятанной" сортировкой

Задача “Предусмотрительное жюри”

“Задачи на олимпиаде будут хорошие:
одну сейчас решает все жюри.
Если не решим, обязательно дадим на олимпиаду!”
Один из членов жюри за месяц до олимпиады

Из правил проведения студенческого командного чемпионата мира по программированию ACM:

Когда команда считает, что она решила задачу, она может послать свое решение на проверку. Решение проверяется на наборе секретных тестов. Если хотя бы один из тестов не проходит, команде сообщается причина (неверный ответ, превышение предела времени и т.д.). Такое решение считается неверным и на результат команды никак не влияет.

Если же решение проходит все тесты, то данная задача считается решенной, и команде начисляется некоторое количество штрафного времени. Штрафное время — это время в минутах от начала тура до момента посылки правильного решения этой задачи на проверку плюс по 20 штрафных минут за каждую неверную попытку по этой задаче (до тех пор, пока решение не прошло все тесты, никакого штрафного времени за задачу не начисляется).

Команды ранжируются по числу решенных задач, а при одинаковом их числе — по штрафному времени (чем штрафное время меньше, тем лучше).

Жюри точно уверено, что команда “Super solvers”, известная своей непобедимостью, все равно за тур успеет решить все задачи, и скорее всего каждую из задач — с первой же попытки (то есть штрафное время за каждую задачу будет равно времени от начала тура до момента ее посылки на проверку). Конечно, жюри может попытаться усложнить задачи, однако оно не хочет этого делать, так как опасается, что в этом случае из остальных команд вообще никто ничего не решит.

Сама команда тоже прекрасно понимает, что ей по силам решить все задачи, поэтому ей все равно, в каком порядке решать задачи, — и команда решила, что будет решать задачи по порядку, начиная с первой.

Среди членов жюри есть тренер этой команды. Он прознал про тактику, которой решила придерживаться команда, а также может примерно оценить время, которое потребуется команде для решения каждой задачи. Жюри прекрасно понимает, что уже никак не может повлиять на число решенных командой задач, но зато, учитывая тактику команды, жюри может влиять на штрафное время, которое получит команда, располагая задачи в разном порядке. В самом деле, если на тур предлагается две задачи, и на решение одной из них команда тратит 10 минут, а на решение второй — 20, то штрафное время команды, если задачи расположить именно в таком порядке, будет равно 40 минутам (первую задачу команда сдает на 10-й минуте тура, вторую — на 30-й, 10 + 30 = 40). Если же задачи расположить в обратном порядке, то штрафное время будет равно 50 (сначала команда потратит 20 минут, потом еще 10, то есть пошлет задачи на 20-й и 30-й минутах, и штрафное время будет равно 20 + 30 = 50).

Жюри хочет, чтобы штрафное время команды “Super solvers” было как можно больше (быть может, это даст хоть какой-то шанс другим командам). Помогите членам жюри расположить задачи в таком порядке.

Формат входных данных

Во входном файле записано сначала число N (1≤N≤20) — количество задач на тур. Затем идет N натуральных чисел, каждое из которых не превышает 300. i-е из этих чисел задает количество минут, которое (по прогнозу тренера) команда “Super solvers” потратит на решение задач номер i.

Формат выходных данных

В выходной файл выведите N чисел, задающих номера задач в той нумерации, которая есть у жюри в данный момент, в том порядке, в каком задачи должны быть расположены на олимпиаде.

Примеры

Входные данные	Выходные данные
1 25	1
2 20 10	1 2
2 10 20	2 1

Решение

Рассмотрим, как будет получаться штрафное время для каждой задачи: это будет сумма текущего времени (потраченного на все уже решенные задачи) и времени, необходимого на решение задачи. По приведенным правилам вполне понятно, что для увеличения времени решения команде надо давать вначале наиболее сложные для нее задачи — тогда для каждой задачи текущее время будет максимальным.

Реализация этого алгоритма довольно проста, но мы рассмотрим некоторые важные моменты, которые могут быть использованы и в других задачах.

Самое первое — формат входных данных. Нам ничего не сказано про переводы строк или пробелы и т.п. Это связано с тем, что при чтении чисел автоматически пропускаются все разделители (пробелы, переводы строк, табуляции). Числа нужно читать только с помощью read! Readln следует использовать только при работе со строками.

Ограничение на количество задач равно 20, а это означает, что мы можем использовать любой алгоритм сортировки (например, “пузырьком”). При этом сортировать нужно по убыванию времени, запоминая номер задачи (он пригодится при выводе). Таким образом, один из способов правильной сортировки — иметь два массива, один со временами (по этому параметру мы и будем сортировать), а второй — с номерами задач в исходной нумерации (их мы будем просто переставлять не сравнивая). Другой способ — хранить два поля: время и номер в записи.

При реализации алгоритма сортировки “пузырьком” не следует делать никаких лишних проверок, например, на то, что массив уже отсортирован и следует прервать работу. Это не даст никакого выигрыша (скорее всего даже даст проигрыш), увеличит время, которое тратится на реализацию алгоритма и увеличивает вероятность ошибки.

После сортировки нам достаточно вывести содержимое массива с номерами — это и есть ответ.

var
a, b : array[1..20] of longint;
i, j, k, n : longint;
begin
read(n);
for i := 1 to n do begin
read(a[i]);
// запоминаем номер в исходном списке
b[i] := i;
end;
for i := 1 to n do
for j := 1 to n — i do
if a[j] < a[j + 1] then begin
k := a[j]; // переставляем время
a[j] := a[j + 1];
a[j + 1] := k;
k := b[j]; // и номера
b[j] := b[j + 1];
b[j + 1] := k
end;
for i := 1 to n do write(b[i], ' ')
end.

Задача “Коррозия металла”

Для хранения двух агрессивных жидкостей A и B используется емкость с многослойной перегородкой, которая изготавливается из имеющихся N листов. Для каждого листа i (i = 1, ..., N) известно время его растворения жидкостью A — a_i и жидкостью B — b_i. Растворение перегородки каждой из жидкостей происходит последовательно лист за листом, с постоянной скоростью по толщине листа. Требуется спроектировать такую перегородку, время растворения которой было бы максимальным.

Формат входных данных

В первой строке входного файла записано число N
(1 ≤ N ≤ 256). В каждой из последующих N строк содержатся два положительных вещественных числа ai и bi, разделенные пробелом.

Формат выходных данных

В первую строку выходного файла записать время растворения перегородки с точностью до 3 цифр после десятичной точки. В следующую строку файла записать номера листов в порядке их расположения от жидкости A к жидкости B, разделяя числа пробелами.

Пример

Входные данные	Выходные данные
4 1 2 1 2 0.5 1.5 7 3.5	6.000 4 2 1 3

Решение

В первую очередь необходимо определиться, в каком порядке следует располагать перегородки, чтобы максимизировать время растворения. Вполне естественна идея, что левее нужно располагать перегородки, которые “дольше” растворяются жидкостью A, а правее те, что “дольше” растворяются жидкостью B.

Осталось понять, что же означает “дольше” в нашей конкретной задаче. Рассмотрим, как будет происходить процесс растворения в общем случае. Часть перегородок будут полностью растворены жидкостью A, часть полностью жидкостью B, а одна перегородка будет растворяться сразу с двух сторон (может оказаться так, что такой перегородки не будет). Относительный порядок растворения перегородок одной жидкостью роли не играет, т.е. фактически нам нужно разделить все перегородки на те, что “слева” и те, что “справа”.

Понятно, что перегородки “слева” должны обладать неким свойством, которое определяет, что их лучше поставить ближе к жидкости A. Вариантов на самом деле не так уж много: разность параметров ai и bi, или их частное (нетрудно заметить, что попытки разделения их по другим соотношениям сразу приводят к плачевному результату).

Если сортировать перегородки по разности ai и bi, то на примере для перегородок (8, 3), (2, 1) мы получим, что слева должна стоять перегородка (8, 3), а справа — (2, 1). Общее время растворения в таком случае будет 2.727, а если расположить их в другом порядке, то время будет 2.909. Для сортировки по отношению параметров контрпримера подобрать не удается.

На олимпиаде по информатике отсутствие контрпримеров и логичность являются достаточными доказательствами правильности идеи. Полное доказательство точности данного метода требует значительного времени и аккуратности.

Мы же сосредоточимся на реализации данного решения. У нас есть некоторый порядок, в котором расположены перегородки, и нам требуется определить время растворения. Эту задачу будем решать простым моделированием.

В нашей модели будет две переменных, указывающих номера перегородок, разъедаемых в данный момент жидкостями A и B соответственно. Из двух времен выберем меньшее (какая перегородка разъестся быстрее), прибавим его к суммарному времени и передвинем соответствующий указатель. После этого вторую перегородку следует уменьшить, вычесть ту часть, которая разъелась за время растворения первой перегородки. При этом уменьшать следует оба параметра ai и bi, это значительно облегчит нам дальнейшую обработку. Тут следует обратить внимание на слова из условия “с постоянной скоростью по толщине листа” и уменьшать оба параметра на соответствующую часть. Также возможен случай, когда перегородки растворятся с обеих сторон одновременно. В некоторых реализациях это чревато делением на ноль на следующем шаге, так что вставим отдельную проверку и, в случае, если у нас возникла такая ситуация, удалим растворенные перегородки (изменим указатель).

Этот процесс следует повторять до тех пор, пока указатели не станут показывать на один и тот же лист или же левый указатель не станет больше правого (две средние перегородки растворились одновременно). Если у нас осталась одна перегородка, то она будет растворяться с суммарной скоростью. Здесь нам поможет то, что на каждом шаге мы пересчитывали оба параметра ai
и bi, и они отражают актуальное состояние перегородки независимо от того, что с ней происходило раньше. По известному времени растворения одной и другой жидкостью суммарное время растворения считается по формуле (a_i x b_i) / (a_i ± b_i).

type
// запись для хранения информации
// о перегородке
wall = record
a, b : extended;
num : longint;
end;
var
w : array[1..256] of wall;
temp : wall;
time : extended;
i, j, k, n : longint;
begin
read(n);
for i := 1 to n do begin
read(w[i].a, w[i].b);
w[i].num := i
end;
// сортировка перегородок по убыванию a/b
for i := 1 to n do
for j := 1 to n — i do
if w[j].a / w[j].b < w[j + 1].a / w[j + 1].b
then begin
temp := w[j];
w[j] := w[j + 1];
w[j + 1] := temp
end;
// номер левой растворяемой перегородки
i := 1;
j := n; // номер правой перегородки
time := 0; // суммарное время растворения
while i < j do begin // пока не сошлись
// левая растворится быстрее правой
if w[i].a < w[j].b then begin
w[j].a := w[j].a * ((w[j].b — w[i].a)/ w[j].b);
// пересчитали оба параметра для правой
w[j].b := w[j].b — w[i].a;
// и увеличили суммарное время
time := time + w[i].a;
inc(i) // левой перегородки больше нет
// все то же самое, если правая быстрее левой
end else begin
w[i].b := w[i].b * ((w[i].a — w[j].b) / w[i].a);
w[i].a := w[i].a — w[j].b;
time := time + w[j].b;
dec(j)
end;
// на случай, если растворились одновременно
if w[i].a = 0 then inc(i);
if w[j].b = 0 then dec(j)
end;
// осталась одна — растворяем сразу с двух сторон
if i = j then time := time + (w[i].a * w[i].b) / (w[i].a + w[i].b);
writeln(time:0:3);
for i := 1 to n do write(w[i].num, ' ')
end.