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

Автор:Н. Чистякова   Ограничение времени: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

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

Автор:А. Кленин, А. Жихарева   Ограничение времени: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
\/

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

Автор:И. Блинов, М. Спорышев, А. Жихарева   Ограничение времени: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

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

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

Условие

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ pi, aij ≤ 1000; 1 ≤ 2 ⋅ N ≤ 2000; 1 ≤ M ≤ 10000; 1 ≤ ki ≤ 106;

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

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

Подзадача Баллы Дополнительные ограничения
2 ⋅ N, Maijpi
1251 ≤ 2 ⋅ N, M ≤ 10001 ≤ aij ≤ 1000pi = 1
2251 ≤ 2 ⋅ N, M ≤ 1000aij = 1 1 ≤ pi ≤ 1000
3251 ≤ 2 ⋅ N, M ≤ 10001 ≤ aij ≤ 10001 ≤ pi ≤ 1000
4251 ≤ 2 ⋅ N ≤ 2000, 1 ≤ M ≤ 100001 ≤ aij ≤ 10001 ≤ pi ≤ 1000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1 3
1 10
2 5 5
1 
5
10
1
1
1
2
2 3
5 1 1 1 1 1
3 1 1 1
1 100
2 4 3
4
200
1
1
-1
3

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

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

Условие

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

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 104

1 ≤ ai ≤ 109

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

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

Подзадача Баллы Дополнительные ограничения
Nai
1301 ≤ N ≤ 201 ≤ ai ≤ 100
2301 ≤ N ≤ 2001 ≤ ai ≤ 106
3401 ≤ N ≤ 100001 ≤ ai ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4
1 3 2 4
YES
2
5
11 35 50 22 41
NO
3
6
13 5 6 1 2 3
YES

0.080s 0.005s 17