Рассмотрим расписание движения электричек на некоторой железнодорожной линии. Нас будут интересовать только электрички, идущие в одном направлении.
Каждая электричка отправляется с некоторой станции и следует до некоторой другой станции со всеми остановками. При этом средняя маршрутная скорость у каждой электрички своя (будем считать, что весь маршрут электричка проходит с этой скоростью, временем стоянки на станциях пренебрежем). Поскольку на участке только один путь в данном направлении — электрички в процессе следования друг друга не обгоняют.
Требуется выпустить книжку-расписание электричек. Обычно такая книжка представляет собой таблицу, где в первом столбце перечислены все станции, а каждый следующий столбец соответствует электричке: если электричка проходит через станцию, то в соответствующей клетке указывается время прохождения этой электрички через эту станцию, и прочерк, если электричка через эту станцию не проходит.
Естественно, что в книжке-расписании нужно расположить электрички так, чтобы они были указаны в хронологическом порядке. А именно, если две электрички имеют хотя бы одну общую станцию (даже если она является начальной станцией для одной, и конечной — для другой электрички), электрички в расписании должны идти в том порядке, в каком они проходят через эту станцию (поскольку электрички не обгоняют друг друга, то это же будет справедливо для всех общих станций этих двух электричек). Если же электрички не имеют ни одной общей станции, то они могут быть указаны в любом порядке.
По данному расписанию движения электричек определите порядок, в котором электрички должны идти в книжке—расписании.
Сначала вводится целое число N (1 ≤ N ≤ 1000) — количество электричек. Далее идёт описание электричек: каждая электричка задается четырьмя числами Ai, Bi, Ci, Di (0 ≤ Ai < Bi ≤ 106, 1 ≤ Ci ≤ 100, 0 ≤ Di ≤ 10000), которые обозначают, что данная электричка отправляется со станции «Ai-й километр» и следует до станции «Bi-й километр». Электричка отправляется с начальной станции в момент Ci. Один километр электричка проезжает за Di секунд.
Гарантируется, что расписание можно составить корректно, в частности, никакая электричка не обгоняет другую.
Выведите последовательность из N номеров от 1 до N – номера электричек в том порядке, в котором они должны идти в книжке-расписании. Если возможных ответов несколько, выведите любой.
Комментарий к примеру тестов
Ответ 2 3 1 также будет верным.
3 1 10 3 4 3 5 3 4 10 11 10 1
3 2 1
Студенты пришли на занятия в большую аудиторию и все сели на какие-то места первого ряда аудитории. Пришедший преподаватель объявил, что сейчас состоится контрольная работа, и решил пересадить студентов так, чтобы никакие два студента не сидели на двух подряд идущих местах (чтобы между любыми двумя студентами всегда было как минимум одно свободное место).
Помогите преподавателю пересадить минимальное число студентов, чтобы достичь нужного результата.
Сначала вводится натуральное число N — количество мест в первом ряду аудитории, а затем число K — количество студентов. Далее в порядке возрастания перечислены номера мест, на которые студенты сели изначально (все места пронумерованы числами от 1 до N).
1 ≤ K ≤ 1000, 2K–1 ≤ N ≤ 109.
Выведите одно число — минимальное количество студентов, которых придется пересадить.
Решение для n <= 15 будет набирать 30 баллов, для n <= 3000 будет набирать 60 баллов.
7 4 2 4 6 7
3
8 4 2 4 6 7
1
В волшебном лесу растут N деревьев. На плане леса они изображены точками (диаметром деревьев можно пренебречь). Территорией леса считается наименьший по площади выпуклый многоугольник (возможно, вырожденный), содержащий в себе все деревья.
Отважный путешественник и писатель Ручкин однажды решился на отчаянный поступок — он совершил путешествие в этот лес. После этого он описал свое путешествие в книге. В частности, в книге описаны все деревья леса в том порядке, в каком они встречались Ручкину (каждое дерево описано ровно один раз).
Художник Кистин решил нарисовать иллюстрацию для этой книги. Для этого он приехал и остановился в деревне недалеко от волшебного леса. Теперь он хочет выбрать точку, с которой он будет рисовать иллюстрацию. Кистин очень боится заходить в волшебный лес, поэтому хочет найти точку для рисования обязательно за пределами леса (в том числе, она не может находиться на границе леса).
Он решил нарисовать весь лес: он хочет взять длинный-длинный холст, и зарисовать весь лес справа налево, от самой правой точки леса до самой левой. При этом деревья леса должны на картине идти справа налево ровно в том же порядке, в котором они описаны в книге. Естественно, никакое дерево не должно быть заслонено другим деревом (т.е. на отрезке между Кистиным и деревом не может быть других деревьев).
Помогите ему: напишите программу, которая по координатам деревьев волшебного леса в том порядке, в каком они описаны у Ручкина, поможет Кистину выбрать точку, из которой деревья видны в требуемом порядке.
Задано число N — количество деревьев в лесу (1 ≤ N ≤ 100000). Далее перечислено N пар чисел, задающих координаты деревьев в том порядке, в каком они описаны в книге Ручкина. Все координаты – целые числа, не превосходящие по абсолютной величине 105. Гарантируется, что никакие два дерева не растут в одной точке.
Если подобрать точку для Кистина возможно, выведите сообщение Possible, а в следующей строке — два вещественных числа: координаты точки. Координаты выведенной точки не должны превышать 1015 по абсолютной величине. Если подобрать точку с указанными ограничениями не удастся, выведите сообщение Impossible.
При проверке ответа для случая Possible он будет считаться верным, если на расстоянии менее 10–5 от выведенной точки будет существовать точка, удовлетворяющая условию.
Примеры
| Входные данные | Выходные данные |
| 3 0 0 1 2 2 1 | Possible 1 4 |
| 3 1 0 2 0 3 0 | Possible 1 1 |
| 3 1 0 3 0 2 0 | Impossible |
| 4 0 0 2 3 4 2 3 1 | Impossible |
| 4 0 0 4 0 2 2 4 4 | Possible -2 2 |
В одной театральной кассе есть в продаже билеты любой стоимости, выражающейся натуральным числом. При покупке билетов по цене за билет от A до B рублей включительно нужно дополнительно оплатить сервисный сбор в размере C процентов от номинальной стоимости билетов (сервисный сбор не обязательно выражается целым числом рублей, но всегда выражается целым числом копеек). При покупке билетов стоимостью менее A рублей за билет, а также более B рублей за билет, сервисный сбор не берется.
У вас есть X рублей и вам нужно K билетов одинаковой цены (цена обязательно должна выражаться натуральным числом рублей, 0 не считается натуральным). Билеты какого самого дорогого номинала вы можете себе позволить?
Вводятся целые A, B, C, X, K (1 ≤ A ≤ B ≤ 109, 0 ≤ C ≤ 1000, 0 ≤ X ≤ 109, 1 ≤ K ≤ 100000).
Если на имеющиеся деньги невозможно приобрести ни одного билета, выведите 0. Иначе выведите натуральное число – номинальную стоимость приобретённых билетов.
Подзадача 1. Все числа \(\le100\) - 50 баллов.
Подзадача 2. Без дополнительных ограничений - 50 баллов.
1 10 0 5 5
1
10 100 50 50 5
9
10 100 50 100 5
13
Завтра Петя уезжает в кругосветное путешествие, в процессе которого собирается посетить N разных городов. Вспомнив о старинной традиции бросать монетки в фонтаны для того, чтобы когда-нибудь вернуться в это место, он решил запастись монетами заранее. Поскольку это всего лишь традиция, подумал Петя, то с него хватит оставить в каждом городе по одной копеечной монете – зачем тратиться зря?
К сожалению, копеечные монеты – достаточно редкая вещь. В частности, таковых у Пети не нашлось. Купюр и монет всех остальных достоинств у него с избытком.
С этими мыслями Петя решил прогуляться до продуктового магазина – купить в дорогу немного еды. Из всего ассортимента ему подходило M видов товара (количество товаров каждого вида неограниченно), стоимость i-го равна ai рублей bi копеек. И тут его осенило. Если покупать товары в правильной последовательности, то он довольно быстро сможет скопить так нужные ему N копеечных монет!
Процесс покупки в магазине устроен следующим образом. Петя может заказать любой набор из подходящих ему товаров (каждого товара Петя может взять сколько угодно единиц). После чего он платит за них и получает сдачу минимальным числом купюр и монет (любых монет и купюр в кассе также с избытком). Это означает, например, что если ему должны сдать 11 рублей и 98 копеек сдачи, то он получит купюру в 10 рублей, монеты в 1 рубль, 50 копеек, 4 монеты в 10 копеек, одну монету в 5 копеек и три копеечных монеты. При этом он волен вносить любую сумму (лишь бы она была не меньше требуемой для оплаты) и платить любым набором купюр и монет, имеющихся у него в распоряжении.
После этого Петя может ещё раз подойти к кассе, сделать заказ, расплатиться имеющимися наличными (можно использовать и полученные до этого со сдачей) и так далее сколько угодно раз.
Петя хочет потратить в этом магазине как можно меньше денег. Помогите ему найти оптимальный способ обретения не менее N копеечных монет с минимальными затратами.
Комментарий для нероссийских участников олимпиады.
В России используются монеты и купюры достоинством 1, 5, 10, 50 копеек и 1, 2, 5, 10, 50, 100, 500, 1000 и 5000 рублей. 1 рубль равен 100 копейкам.
Сначала вводятся целые числа N и M (0 ≤ N ≤ 108, 0 ≤ M ≤ 100) — количество городов, которые собирается посетить Петя, и количество подходящих ему видов товара. Далее идут M пар чисел ai, bi, обозначающих стоимость товара соответствующего типа (0 ≤ ai ≤ 100, 0 ≤ bi ≤ 99). Стоимость товара всегда больше нуля.
Если требуемое количество копеечных монет получить невозможно, выведите –1. Иначе выведите минимальную сумму, которую должен потратить Петя на покупку товаров, чтобы получить N однокопеечных монет. Сумма должна быть выведена как два целых числа, задающих рубли и копейки (второе число обязано быть от 0 до 99).
3 1 0 2
0 2
4 2 1 2 0 4
0 16
1 3 0 1 0 4 0 6
0 1