Задача A. Дипломы ≡

Условие

Когда Петя учился в школе, он часто участвовал в олимпиадах по информатике, математике и физике. Так как он был достаточно способным мальчиком и усердно учился, то на многих из этих олимпиад он получал дипломы. К окончанию школы у него накопилось N дипломов, причем, как оказалось, все они имели одинаковые размеры: W — в ширину и H — в высоту.

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

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

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

Решения, правильно работающие только при W, H, N ≤ 1000, будут оцениваться в 40 баллов.

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

Входной файл содержит три целых числа: W, H, N

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

В выходной файл необходимо вывести ответ на поставленную задачу.

Ограничения

1 ≤ W, H, N ≤ 10⁹

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

2 3 10

9

Задача B. Паркет ≡

Условие

Андрей укладывает дома пол. У него длинный коридор длиной L.

У Андрея есть бесконечное количество досок, длины которых равны d. Необходимо полностью уложить пол досками. Доски можно пилить, но при этом в укладке нельзя использовать части досок короче c.

Сколько досок Андрею необходимо разрезать, чтобы уложить пол?

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

Входные данные содержат три целых числа: L, d, c.

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

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

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

Ограничения

1 ≤ L, d ≤ 10⁹

0 ≤ c ≤ 10⁹

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

10 2 2

0

10 3 2

2

100 9 9

-1

Задача C. Эффективное чтение ≡

Условие

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

Более формально, занумеруем дни учебного семестра начиная с 1. Пете для учебы необходимо N книг. Занумеруем их числами от 1 до N. Для книги с номером i известны три числа:

• L_i — номер дня, в который книгу следует взять в библиотеке;
• R_i — номер дня, в который книгу следует отдать;
• p_i — количество страниц в книге.

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

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

В приведённом примере имеется 2 книги и 3 дня для чтения (в день номер 4 Петя приходит в библиотеку утром). В первый день Петя берёт в библиотеке книгу с номером 1 и прочитывает, например, 30 страниц из неё. Во второй день Петя берёт книгу с номером 2. Поскольку эту книгу необходимо отдать в следующий день, все её 50 страниц следует прочесть в день с номером 2. На третий день Петя относит книгу 2 в библиотеку и дочитывает оставшиеся 30 страниц первой книги. Таким образом, Петя может прочесть обе книги, читая не более 50 страниц в день. С другой стороны, ответ не может быть меньше 50, поскольку вторую книгу нужно прочесть за один день.

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

N = 1;

N ≤ 10³;

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

Входной файл содержит целое число N, за которым следует N троек целых чисел L_i R_i p_i.

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

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

Ограничения

1 ≤ N ≤ 10⁵;

1 ≤ L_i < R_i ≤ 10⁵;

1 ≤ p_i ≤ 10⁵;

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

2
1 4 60
2 3 50

50

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

Условие

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

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

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

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

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

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

Первая строка входного файла содержит число n — количество частиц. Последующие n строк описывают частицы следующим образом: каждая строка содержит по два целых числа x_i и v_i — координату i-й частицы и ее тип соответственно (x₁ < x₂ < x₃ < ... < x_n). Частица e⁻ описывается значением v_i = −1, а частица e⁺ описывается значением v_i = 1.

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

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

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

Ограничения

1 ≤ n, m ≤ 200000

−10⁹ ≤ x_i, m ≤ 10⁹

0 ≤ t_i ≤ 10⁹

v_i равно −1 или 1

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

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

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

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

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

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

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

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

4
-1 1
0 -1
1 1
5 -1
4
0 1 2 3

4
2
0
0

Задача E. Коктейль ≡

Условие

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

Для приготовления коктейля требуется p_i% i-го сока (p_i% — массовая доля). В наличии имеется a_i граммов i-го сока. Сколько граммов коктейля можно приготовить?

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

Входной файл содержит целое число N, за которым следуют N пар целых чисел p_i a_i.

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

Требуется вывести в выходной файл единственное число — массу коктейля в граммах с точностью не менее 3-х знаков после запятой.

Ограничения

1 ≤ N ≤ 100

1 ≤ a_i ≤ 1000

1 ≤ p_i ≤ 100

p₁ + p₂ + … + p_N = 100

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

2
50 300
50 400

600.000

3
20 30
30 40
50 39

78.000

Задача F. Перетягивание канатов ≡

Условие

На уроке физкультуры дети решили поиграть в перетягивание канатов. Чтобы игра была интересной, им нужно разделиться на две команды, как можно меньше различающиеся по силе. Кроме того, одного школьника следует назначить судьей, который будет следить за тем, чтобы поединок проходил честно.

Дети обратились к самому умному ученику в классе, Васе, с просьбой поделить их на две команды и выбрать судью.

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

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

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

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

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

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

Ограничения

3 ≤ N ≤ 30.

0 ≤ a_i ≤ 10⁷.

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

3
1 2 3
    

1

3
1 10 10
    

0