Задача A. Сонный пассажир

Автор:А. Щуров   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

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

Длительность полета T часов. Об удачном взлете объявляют через S минут после начала полета, об обеде — спустя D минут после начала полета. О предстоящей посадке — за E минут до конца полета.

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

Формат входного файла

Входной файл содержит четыре целых числа T S D E. Гарантируется, что объявление об удачном взлете прозвучит раньше объявления об обеде, а объявление об обеде — раньше объявления о посадке.

Формат выходного файла

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

Ограничения

1 ≤ T ≤ 104

0 ≤ S, D, E ≤ 104

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
1 10 30 5
25
2
1 0 30 0
30

Задача B. Угощение

Автор:Н. Чистякова   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

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

Тесто для пирожных состоит из 200 гр. воды, 125 гр. масла, 160 гр. муки и 5 яиц. Одного замеса теста хватает на 30 пирожных. Крем состоит из 350 гр. масла и 1 банки сгущёнки, одной порции крема хватает на 40 пирожных. Ноэль боится, что если она попытается приготовить смесь из уменьшенного количества ингредиентов, то тесто (или ещё хуже, крем) не получится, и праздник будет испорчен.

В распоряжении Ноэль есть N гр. муки, M гр. масла, K гр. воды, L яиц и P банок сгущёнки, и ей хочется узнать, какое максимальное количество наполненных кремом пирожных она сможет приготовить из этих ингредиентов.

Формат входного файла

Входной файл содержит пять целых чисел: N M K L P

Формат выходного файла

В выходной файл следует вывести единственное число — количество пирожных.

Ограничения

0 ≤ N, M, K, L, P ≤ 1012

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
1000 1000 2000 15 4
60

Задача C. Три точки на букву

Автор:А. Кленин, А. Жихарева   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

Юный программист Вася решил создать свой язык, состоящий из всего четырех букв, которые выглядят так: '//', '\\', '/\' и '\/'.

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

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

Если при рассмотрении точек слева направо их координаты y образуют возрастающую последовательность, то это буква '//'. Если убывающую — '\\'. Если последовательность точек сначала возрастает, потом убывает, это буква '/\'. Если сначала убывает, потом возрастает — '\/'.

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

Отправка решения и тестирование

Данная задача будет проверяться на ОДНОМ входном файле, содержащем все тесты. Этот файл можно скачать ЗДЕСЬ.

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

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

Формат входного файла

Первая строка входного файла содержит целое число N — количество букв. Последующие N строк содержат по 6 целых чисел — x1, y1, x2, y2, x3, y3 — координаты точек буквы в произвольном порядке.

Формат выходного файла

Выходной файл должен содержать N строк — '//', '\\', '/\', либо '\/' — названия соответствующих букв.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
1
2 0 1 4 3 5
\/

Задача D. План эвакуации

Автор:И. Блинов, М. Спорышев, А. Жихарева   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

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

Коридор является одномерным и состоит из N клеток, в каждой клетке может находиться только один человек

План эвакуации представляет из себя строку из N символов 'L', 'R', 'X'. Символ 'L' означает, что человек, находящийся в данной клетке, в случае эвакуации должен пойти в соседнюю клетку слева. Аналогично, символ 'R' означает, что следует пойти вправо. Символ 'X' означает, что в этой клетке расположен выход.

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

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

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

Формат входного файла

Первая строка входного файла содержит числа N, M и K — размер описания плана эвакуации, количество выходов и ограничение на каждый выход.

Вторая строка входного файла содержит M целых чисел xi — координаты выходов. Координаты заданы в порядке возрастания.

Формат выходного файла

В выходной файл выведите единственную строку — описание плана эвакуации, удовлетворяющего всем вышеописанным условиям, или строку NO, если такого плана не существует.

Ограничения

1 ≤ M ≤ N ≤ 105

1 ≤ K ≤ 105

1 ≤ xi ≤ N

Описание подзадач и системы оценивания

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

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

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

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи
N, K
1 25 1 ≤ N ≤ 102
2 20 1 ≤ N ≤ 105, K = N
3 20 1 ≤ N ≤ 104 1
4 35 1 ≤ N ≤ 105 1-3

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
6 1 7
5
RRRRXL
2
10 1 5
5
NO

0.300s 0.017s 21