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

Условие

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

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

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

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

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

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

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

Ограничения

0 ≤ N, M, K, L, P ≤ 10¹²

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

1000 1000 2000 15 4

60

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

Условие

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

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

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

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

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

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

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

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

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

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

Первая строка входного файла содержит целое число N — количество букв. Последующие N строк содержат по 6 целых чисел — x₁, y₁, x₂, y₂, x₃, y₃ — координаты точек буквы в произвольном порядке.

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

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

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

1
2 0 1 4 3 5

\/

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

Условие

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

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

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ M ≤ N ≤ 10⁵

1 ≤ K ≤ 10⁵

1 ≤ x_i ≤ N

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

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

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

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

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

6 1 7
5

RRRRXL

10 1 5
5

NO

Задача D. Реорганизация авиакомпании ≡

Условие

На данный момент авиаперевозчик Аэроплот имеет парк из 2 ⋅ N самолётов. Руководство компании Аэроплот решило провести реорганизацию компании, а именно разделить компанию на две с парком в N самолётов каждая. Одна из компаний будет иметь прежнее название Аэроплот, а другая получит название Беда, и будет предоставлять услуги авиаперевозок по сниженным тарифам.

При разделении самолётов между авиакомпаниями должны выполняться следующие требования:

1. Каждый самолёт компании Аэроплот должен иметь уровень комфорта как минимум k.
2. Каждый самолёт компании Беда должен иметь уровень комфорта меньше чем k.

Для каждого из 2 ⋅ N самолётов известен список доступных пассажиру опций, всего p_i опций для самолёта с номером i. Опция номер j увеличивает суммарный комфорт самолёта номер i на a_ij. Уровень комфорта самолёта с номером i — это сумма значений доступных в нём опций.

Руководство ещё не определилось со значением k и просит вас посчитать для M различных значений k минимальное количество опций, которые следует удалить из всех самолётов суммарно, чтобы самолёты можно было разделить между двумя авиакомпаниями, чтобы выполнить перечисленные условия.

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

Первая строка входного файла содержит целые числа N и M. Далее следует 2 ⋅ N строк, описания самолётов. Первое целое число в строке p_i — количество опций самолёта с номером i, далее следует p_i целых чисел a_ij — опции самолёта i. Далее следует M целых чисел k_i.

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

Выходной файл должен содержать M целых чисел — минимальное количество опций, которые нужно удалить из всех самолётов суммарно для каждого из заданных k_i. Если для какого-то k_i невозможно разделить самолёты заданным способом, следует вывести −1.

Ограничения

1 ≤ p_i, a_ij ≤ 1000; 1 ≤ 2 ⋅ N ≤ 2000; 1 ≤ M ≤ 10000; 1 ≤ k_i ≤ 10⁶;

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

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

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

1 3
1 10
2 5 5
1 
5
10

1
1
1

2 3
5 1 1 1 1 1
3 1 1 1
1 100
2 4 3
4
200
1

1
-1
3

Задача E. Коробки в коробках ≡

Условие

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

Они решили поиграть в игру с коробками.

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

Если в коробке A уже лежат другие коробки, то в нее можно сложить новую коробку только в случае, если её размер меньше всех уже вложенных в A коробок. Иными словами, коробки складываются на манер матрёшек.

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

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

Первая строка входного файла содержит целое число N — количество коробок.

Следующая строка содержит N целых чисел a_i — размеры коробок. Гарантируется, что все размеры различны.

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

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

Ограничения

1 ≤ N ≤ 10⁴

1 ≤ a_i ≤ 10⁹

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

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

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

4
1 3 2 4

YES

5
11 35 50 22 41

NO

6
13 5 6 1 2 3

YES