Задача A. Лифты

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

Условие

N людей хотят попасть на L этаж. Сейчас они находятся на нулевом этаже. Они могут воспользоваться лифтами, коих E штук. Вместимость каждого лифта равна V. Каждый лифт может двигаться вверх и вниз со скоростью один этаж в секунду. Пешком по лестнице человек поднимается на один этаж за T секунд. Вместимость лестницы бесконечна. Какое минимальное количество времени должна потратить эта группа людей, чтобы всем оказаться на L этаже?

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

Входные данные содержат пять целых чисел: N, L, E, V, T.

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

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

Ограничения

1 ≤ N ≤ 109

1 ≤ L, E, V, T ≤ 103

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2 4 1 1 1
4
2
20 4 2 5 1000
12

Задача B. Карточный фокус

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

Условие

Слон Пахом выучил карточный фокус и теперь показывает его всем. Суть фокуса в том, что слон должен отгадать карту, которую загадал игрок. Фокус выполняется следующим образом: берётся колода, состоящая из n карт, и совершается несколько итераций. На каждой итерации все карты раскладываются в m стопок по n/m карт в каждой. Пахом сам выбирает, как раскладывать карты. Далее игрок говорит, в какой стопке лежит карта, которую он загадал. Если слон Пахом уже может однозначно назвать карту, которую загадал игрок, то фокус заканчивается.

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

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

Первая строка входного файла содержит целые числа n, m.

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

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

Ограничения

2 ≤ n, m ≤ 109

n делится на m нацело.

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

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

Задача C. Контроль за выловом рыбы

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

Условие

Всего для вылова доступно P видов рыб. Известно, что компания владелец рыболовного судна получила квоты на вылов wi килограмм i-го вида рыбы.

Рыболовное судно выловило N рыб, i-я рыба имеет вес mi. Каждая из выловленных рыб отнесена к одному из P видов.

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

Рыбиспектор хочет узнать, могло ли случиться так, что какого-то вида рыбы было выловлено больше, чем разрешено по квоте.

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

Первая строка входного файла содержит целые числа P, N, K. Во второй строке содержится P целых чисел wi — размер квоты в килограммах на вылов рыбы вида i. В третьей строке содержится N пар целых чисел mi и ti — масса и вид, к которому отнесли рыбу с номером i рыболовы.

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

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

Ограничения

1 ≤ N, P ≤ 105, 0 ≤ K ≤ 105, 1 ≤ wi, mi ≤ 109, 1 ≤ ti ≤ P

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

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

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
1501 ≤ N, P ≤ 102, 0 ≤ K ≤ 102полная
2501 ≤ N, P ≤ 105, 0 ≤ K ≤ 1051полная

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

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

0.206s 0.028s 11