#3140

Феодальные отношения

Темы: ["Длинная" арифметика]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, Московская областная олимпиада, 2008, Задача B ]

Во Флатландии с некоторых пор процветают феодальные отношения – у каждого порядочного феодала есть ровно два вассала, у непорядочных – вассалов нет совсем. Каждый феодал строит свой замок в городе на прямой, при этом:

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

Для удобства замки феодалов занумерованы натуральными числами по порядку слева направо, начиная с единицы, и разбиты на улицы. Улица (i, j) представляет собой последовательность подряд идущих замков, начиная с замка под номером i и заканчивая замком с номером j (i ≤ j)

Однажды в город приехал новый феодал и пожелал выкупить там замок у одного из жителей. Также ему стало интересно узнать социальный статус соседей по улице, однако, город к тому времени так разросся, что феодал уже не мог сделать этого самостоятельно. Напишите программу, которая поможет ему!

Входные данные

Первая строка входного файла содержит число N (1 ≤ N ≤ 30000) — высота замка единственного главного феодала в городе, который никому не подчиняется. Далее, в следующих двух строках идут числа i и j (\(0 \leq i, j < 10^{10000}\)), задающие улицу (i, j), на которой хочет приобрести замок новый феодал (гарантируется, что замки с номерами i и j находятся в черте города, i ≤ j, j – i ≤ 10⁵).

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

Примечание

Будут оцениваться и частичные решения задачи при малых N. Частичные решения для N<20 набирают до 40 баллов, а для N<50 набирают не более 70 баллов.

Ввод	Вывод
2 1 3	1 2 1
3 3 7	1 3 1 2 1
50 128873293 128873293	1

#3142

Автозаправки

Темы: [Быстрая сортировка]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, Московская областная олимпиада, 2008, Задача D ]

Фирма «АйОйЛ» построила на скоростном шоссе Москва-Тверь N автозаправок. Каждая автозаправка имеет свой номер, который присваивался ей при строительстве, начиная с единицы. Кроме того, каждая автозаправка располагается на определенном километре шоссе. Километры на шоссе нумеруются от 0, начиная от Москвы.

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

Требуется написать программу, которая находит автозаправку, которую можно сократить.

Входные данные

Первая строка входного файла содержит количество автозаправок N (2 ≤ N ≤ 10⁵). Вторая строка входного файла содержит N различных целых чисел x_i – километр, на котором расположена автозаправка с номером i (1 ≤ i ≤ N). Числа в строке разделены пробелом. Значения всех x_i не меньше ноля и не превосходят 10⁹ по абсолютной величине.

Выходные данные

В первой строке выходного файла необходимо вывести номер автозаправки, которую можно сократить. Если ответов несколько, выведите любой из них.

Ввод	Вывод
5 10 3 7 2 5	4

#3143

Перевес багажа

Темы: [Задача о рюкзаке] [Перебор с отсечением]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, Московская областная олимпиада, 2008, Задача E ]

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

У Пети в чемодане лежат N предметов, каждый предмет имеет свой вес W_i килограмм и ценность A_iрублей, причем оказалось так, что для любого предмета выполняется следующее неравенство:

W₁+ W₂+ … + W_i_-1≤ W_i

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

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

Входные данные

В первой строке задаётся количество предметов в багаже у Пети N (1 ≤ N ≤ 50) и какой у Пети перевес чемодана в килограммах M (1 ≤ M ≤ 10¹⁸). Во второй строке задаются N целых неотрицательных чисел – вес всех вещей W_i, сумма чисел не превышает 10¹⁸. В третьей строке заданы N целых неотрицательных чисел – ценность всех вещей A_i, все числа не превышают 10⁹.

Выходные данные

В выходной файл требуется вывести минимальную суммарную стоимость предметов, которые Петя будет вынужден оставить в аэропорту.

Ввод	Вывод
4 15 5 10 15 30 1 5 3 6	3
3 2 1 2 4 7 6 5	5