Задача A. Гаджет в кредит

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

Условие

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

В магазине Васе объяснили правила предоставления кредита.

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

Рекомендуется рассмотреть частичные решения

  1. P=0
  2. C,P103

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

Входной файла содержит целые числа NPC.

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

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

Ограничения

1C109; 0P109; 1N104

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1 0 1
1
2
1 124 12
8
3
1 1 12
2

Задача B. Большой линейный коллайдер

Автор:Центральная предметно-методическая комиссия   Ограничение времени:3 сек
Входной файл:linear.in   Ограничение памяти:256 Мб
Выходной файл:linear.out  

Условие

Группа ученых работает в международной научной лаборатории, которая занимается исследованиями поведения элементарных частиц в установке для экспериментов "Большой линейный коллайдер" (БЛК). Установка БЛК представляет собой прямую, в некоторых точках которой размещаются частицы, которые могут перемещаться вдоль прямой.

В очередном эксперименте в БЛК размещаются n частиц, каждая из которых представляет собой либо отрицательно заряженную частицу — электрон e, либо положительно заряженную частицу — позитрон e+. В эксперименте i-я частица исходно размещается в точке с координатой xi. После начала эксперимента в результате работы БЛК частицы начнут перемещаться в разные стороны вдоль прямой: e частицы перемещаются по направлению уменьшения координаты, а e+ частицы — по направлению увеличения координаты. Абсолютные величины скоростей всех частиц одинаковы и равны 1.

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

Ученые выбрали m различных моментов времени t1,t2,...,tm, для каждого из которых их интересует, какое количество частиц находится в БЛК непосредственно после каждого из этих моментов времени. Отсчет времени начинается с момента 0, когда частицы приходят в движение. Частицы, исчезнувшие в результате взаимодействия в момент времени tj, не должны учитываться при подсчете количества частиц для этого момента времени.

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

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

Первая строка входного файла содержит число n — количество частиц. Последующие n строк описывают частицы следующим образом: каждая строка содержит по два целых числа xi и vi — координату i-й частицы и ее тип соответственно (x1<x2<x3<...<xn). Частица e описывается значением vi=1, а частица e+ описывается значением vi=1.

Следующая строка содержит целое число m — количество моментов времени, которые выбрали ученые. Последняя строка содержит m целых чисел: t1,t2,...,tm.

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

Для каждого момента времени во входном файле требуется вывести одно число: количество частиц в БЛК непосредственно после этого момента.

Ограничения

1n,m200000

109xi,m109

0ti109

vi равно 1 или 1

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

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

Подзадача Баллы Ограничения Необходимые подзадачи
nximti
1351n100100xi100m=10ti100
2121n100109xi109m=10ti1091
3121n200000109xi109m=10ti1091,2
4411n200000109xi109 1m2000000ti1091,2,3

Получение информации о результатах окончательной проверки

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

Пояснение к примеру

В приведенном примере в начальный момент в БЛК находятся 4 частицы: частица e+ в точке 1, частица e в точке 0, частица e+ в точке 1 и частица e в точке 5.

В момент времени 0.5 первая частица e+ и первая частица e сталкиваются в точке с координатой 0.5 и исчезают. В момент времени 1 оставшиеся две частицы находятся в точках с координатами 2 и 4, соответственно. В момент времени 2 они сталкиваются в точке 3 и исчезают. Больше в БЛК частиц нет.

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

Входной файл (linear.in) Выходной файл (linear.out)
1
4
-1 1
0 -1
1 1
5 -1
4
0 1 2 3
4
2
0
0

Задача C. k-я порядковая статистика

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

Условие

K-й порядковой статистикой N-элементного массива называется число Аk, которое будет стоять на K-м месте после сортировки этого массива по возрастанию.

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

Входной файл содержит числа NK, за которыми следуют N чисел — массив для которого следует подсчитать K-ю порядковую статистику.

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

Выходной файл должен содержать K-ю порядковую статистику исходного массива.

Ограничения

1N106, 1KN, 231Ai2311

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

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

Задача D. Кондиционеры

Автор:Центральная предметно-методическая комиссия по информатике   Ограничение времени:2 сек
Входной файл:cond.in   Ограничение памяти:256 Мб
Выходной файл:cond.out  

Условие

При реализации проекта «Умная школа» было решено в каждый учебный класс выбранной для этого школы установить по кондиционеру нового поколения для автоматического охлаждения и вентиляции воздуха. По проекту в каждом классе должен быть установлен только один кондиционер и мощность кондиционера должна быть достаточной для размеров класса. Чем больше класс, тем мощнее должен быть кондиционер.

Все классы школы пронумерованы последовательно от 1 до n. Известно, что для каждого класса с номером i, требуется ровно один кондиционер, мощность которого больше или равна ai ватт.

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

Пояснения к примерам

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

Во втором примере оптимально будет установить в первом и втором классах кондиционеры четвертого типа, а в третьем классе — кондиционер третьего типа. Суммарная стоимость этих кондиционеров будет составлять 13 рублей (3+3+7).

Система оценивания

Частичные решения для n,m1000 будут оцениваться из 50 баллов.

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

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

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

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

Далее, в каждой из m строк содержится пара целых чисел bj и cj — мощность в ваттах j-й модели кондиционера и его цена в рублях соответственно.

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

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

Ограничения

1n50000;

1ai1000;

1m50000

1bj1000,1cj1000;

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

Входной файл (cond.in) Выходной файл (cond.out)
1
1
800
1
800 1000
1000
2
3
1 2 3
4
1 10
1 5
10 7
2 3
13

0.456s 0.037s 13