#1099

Скидки

Темы: [Квадратичные сортировки]

Источники: [ Личные олимпиады, Открытая олимпиада школьников, 2007, Задача C ]

В супермаркете проводится беспрецедентная акция – «Покупая два любых товара, третий получаешь бесплатно*», а внизу мелким шрифтом приписано «* - из трех выбранных вами товаров оплачиваются два наиболее дорогих».

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

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

Во входном файле задано сначала число N (1≤N≤1000), а затем N чисел – стоимости выбранных Васей товаров. Все стоимости – натуральные числа, не превышающие 10000.

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

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

Комментарии к примерам тестов

1. Вася сначала пройдет через кассу с товарами стоимостью 1, 3 и 4 – заплатит 7 рублей и товар стоимостью 1 получит в подарок, а затем снова зайдет в супермаркет и купит товары стоимостью 5 и 7, еще один товар стоимостью 5 получив в подарок.

2. Вася в первый заход в супермаркет купит товары стоимостью 15 и 25 рублей, в качестве подарка взяв товар стоимостью 8 рублей. А во второй заход в супермаркет купит товары стоимостью 3 и 8, не взяв никакого подарка.

Примеры

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

6
1 5 4 3 5 7

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

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

5
3 15 25 8 8

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

#1387

Предпраздничная суета

Темы: [Сортировка подсчетом] [Бинарный поиск по ответу] [Быстрая сортировка]

Источники: [ Личные олимпиады, Открытая олимпиада школьников, 2008-2009, Заключительный этап, Задача C ]

Помимо открыток Петя и Вася решили устроить одноклассницам чаепитие и заразили своей идеей еще K–2 своих друзей. Они собрались вместе и выбрали в одном довольно известном супермаркете P тортиков. Настал черед рассчитываться за них.

В магазине есть N работающих касс, занумерованных числами от 1 до N. Про i-ю кассу известно, что кассиру требуется A_i единиц времени на обработку одного товара и B_i единиц времени для того, чтобы рассчитаться с покупателем. Обойдя все кассы, школьники посчитали, что на обслуживание покупателей, уже стоящих в i-ю кассу, уйдет T_i единиц времени.

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

Напишите программу, которая определит это минимальное время.

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

В первой строке записано одно число N — количество касс в супермаркете (1 ≤ N ≤ 100000). В следующих N строках записано по три числа A_i, B_i, T_i(0 ≤ A_i, B_i, T_i ≤ 100000). В последней строке записаны два числа — K и P — число школьников и покупок у них соответственно (0 ≤ P ≤ 100000, 2 ≤ K ≤ 100000).

Все числа во входном файле целые.

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

Выведите минимальное время выхода последнего школьника из магазина.

Комментарии к примерам тестов

Здесь лучше всего встать в обе кассы и купить там по одному тортику.

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

Частичные ограничения

Первая группа состоит из тестов, в которых N ≤ 10 и оценивается в 30 баллов.

Вторая группа состоит из тестов, в которых N ≤ K ≤ 100000 и оценивается в 30 баллов.

Третья группа состоит из тестов без дополнительного ограничения и оценивается в 40 баллов.

Примеры

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

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

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

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

#1744

Игра с фишками

Темы: [Алгоритмы сортировки] [Простые игры]

Источники: [ Личные олимпиады, Открытая олимпиада школьников, 2008-2009, Заочный этап, Задача D ]

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

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

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

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

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

Сначала вводится число \(N\) — количество карточек с числами (1≤\(N\)≤100000). Далее записаны \(N\) натуральных чисел — числа, написанные на карточках. Каждое из этих чисел не превышает 10000.

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

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

Примеры

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

4
5 1 8 2

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

11
7

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

5
9 6 3 7 10

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

21
16

#1978

Расписание электричек

Темы: [Алгоритмы сортировки] [Обход в глубину]

Источники: [ Личные олимпиады, Открытая олимпиада школьников, 2009-2010, Заключительный этап, Задача B ]

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

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

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

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

По данному расписанию движения электричек определите порядок, в котором электрички должны идти в книжке—расписании.

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

Сначала вводится целое число N (1 ≤ N ≤ 1000) — количество электричек. Далее идёт описание электричек: каждая электричка задается четырьмя числами A_i, B_i, C_i, D_i (0 ≤ A_i < B_i ≤ 10⁶, 1 ≤ C_i ≤ 100, 0 ≤ D_i ≤ 10000), которые обозначают, что данная электричка отправляется со станции «A_i-й километр» и следует до станции «B_i-й километр». Электричка отправляется с начальной станции в момент C_i. Один километр электричка проезжает за D_i секунд.

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

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

Выведите последовательность из N номеров от 1 до N – номера электричек в том порядке, в котором они должны идти в книжке-расписании. Если возможных ответов несколько, выведите любой.

Комментарий к примеру тестов

Ответ 2 3 1 также будет верным.

Примеры

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

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

3 2 1

#3204

Отрезки на прямой возвращаются

Темы: [Сканирующая прямая] [Список]

Источники: [ Личные олимпиады, Открытая олимпиада школьников, 2010-2011, Заочный этап, Задача J ]

На прямой задано \(N\) попарно различных отрезков \([a_i, b_i]\) (\(i = 1, 2, \dots, N\), \(a_i < b_i\)). Будем говорить, что отрезок номер \(i\) непосредственно содержится в отрезке номер \(j\) (\(i \ne j\)), если:

он полностью принадлежит \(j\)-му (то есть \(a_j \le a_i\) и \(b_i \le b_j\)),
среди заданных \(N\) отрезков не найдётся такого отрезка (с номером \(k\)), что \(i\)-й отрезок принадлежит \(k\)-му и \(k\)-й принадлежит \(j\)-му (здесь \(i\), \(j\) и \(k\) - различные числа).

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

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

Сначала вводится целое число \(N\) (\(1 \le N \le 100\,000\)). Далее идут \(N\) пар целых чисел \(a_i\), \(b_i\) (\(-10^9 \le a_i < b_i \le 10^9\)).

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

Выведите \(N\) чисел. Число номер \(i\) должно быть равно номеру отрезка, в котором непосредственно содержится отрезок номер \(i\), либо 0 - если такого не существует.

Если существует несколько решений, выведите любое.

Примечания

Тесты состоят из четырёх групп.

Тест 1, из условия, оценивается в 0 баллов.
Тесты 2--11. В них \(N \le 100\). Группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
Тесты 12--27. В них \(N \le 10\,000\). Группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
Тесты 28--35. Off-line группа, полные ограничения. Каждый тест оценивается в 5 баллов (тесты оцениваются независимо друг от друга). При этом баллы за тесты этой группы ставятся только тогда, когда программа проходит все тесты групп 1 и 2. Если программа не проходит хотя бы один из тестов групп 1 и 2, то баллы за тесты группы 3 не ставятся.

Примеры

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

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

3 4 0 0