Штанга (Barbell)

Гномы хорошо знают, насколько важны занятия спортом, поэтому часто ходят в тренажёрный зал. Впрочем, заниматься уборкой после изнурительной тренировки совсем не хочется, так что большинство тренажёров остаются в состоянии «как получилось». Администратору зала особые хлопоты причиняют штанги (оказывается, снять все «блины» в одиночку довольно сложно).

Штанга – спортивный снаряд, состоящий из грифа (металлического стержня) массой M, размещённый на двух опорах, отдалённых от центра масс грифа на L. Слева от левой опоры плотно размещены N блинов, каждый ширины 2W массы A_i. Эти N блинов нумеруются, начиная от опоры (справа налево). Справа от правой опоры аналогичным образом размещены K блинов, каждый ширины также 2W и массы B_i. Эти K блинов нумеруются, начиная от опоры (слева направо).

Гном-администратор умеет быстро снимать блины (разумеется, начиная от крайнего), но довольно медленно переходит со стороны на сторону. Кроме того, гному совсем не хочется, чтобы в какой-то момент времени штанга опрокинулась (то есть, чтобы её центр масс оказался за пределами опор; если центр масс оказывается ровно на некоторой из опор, штанга не опрокидывается). В начальный момент времени штанга не опрокидывается, то есть центр масс всей конструкции находится между левой и правой опорами (возможно, ровно на одной из опор). Администратор хочет выбрать сторону, с которой начинать, подойти к ней, снять некоторое количество крайних блинов, после чего сменить сторону, повторить те же действия, потом опять сменить сторону и продолжать, пока возможно снимать хотя бы один блин без опрокидывания всей конструкции.

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

С самого начала гном может выбрать сторону «бесплатно», то есть в общее количество смен стороны этот выбор не включается.

Формат ввода-вывода:

Программа Barbell читает с клавиатуры (стандартного устройства ввода) три строки. В первой строке находятся четыре числа: M, L, W, N, K (1 ≤ M, L, W, N, K ≤ 10⁵) – соответственно, масса грифа, половина расстояния между опорами, половина ширины каждого из блинов и количества блинов на правой и на левой половине.

Во второй строке ровно N целых неотрицательных чисел, каждое не превышает 10³ – масса каждого из блинов, размещённых справа.

В третьей строке ровно K натуральных чисел, каждое не превышает 10³ – масса каждого из блинов, размещённых слева.

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

Пример входных и выходных данных

Изображение ко второму тесту

- - - - - - - - - - - - - - - - - - - - - - - - -

Выпуклые оболочки (ConvexHulls)

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

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

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

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

Формат ввода-вывода:

Сначала программа ConvexHulls считывает с клавиатуры (стандартного устройства ввода) число n (3 ⩽ n ⩽ 2 · 10⁵) - количество точек множества. Далее в следующей строке считываются пары целых чисел, которые не превышают по модулю 10⁹ - координаты точек. Гарантируется, что никакие две точки не совпадают.

Программа ConvexHulls выводит на экран (стандартное устройства вывода) два числа через пробел p q, де p, q – целые неотрицательные числа.

Пример входных и выходных данных

- - - - - - - - - - - - - - - - - - - - - - - - -

Экзамены (Exams)

Одним прекрасным утром студент проснулся и понял: скоро сессия! Студент знает, сколько времени (от данного момента) осталось до начала каждого экзамена, и сколько времени требуется на подготовку к каждому экзамену. Студент сдаёт экзамены моментально. Кроме того, студент умеет готовиться к экзаменам как непрерывно, так и с разрывами на подготовку к другим экзаменам и/или на сдачу других экзаменов (всё это не влияет на суммарную длительность подготовки).

Какое максимальное количество экзаменов может сдать студент?

Формат ввода-вывода:

Программа Exams читает с клавиатуры (стандартного устройства ввода) целое число n (0<=n<=10000) и далее n пар целых чисел T_i, D_i (0<=T_i<1000000, 0<D_i<1000000, все T_i попарно различны) – момент начала и длительность подготовки для i-го экзамена. Все числа разделены пробелами.

Программа Exams выводит на экран (стандартное устройство вывода) единственное целое число: максимальное количество экзаменов, которые студент может.

Пример входных и выходных данных

- - - - - - - - - - - - - - - - - - - - - - - - -

Нелюбимые цифры (Numbering)

Новый руководитель организации обнаружил, что его предшественник, по одному ему известным причинам, для нумерации официальных документов принципиально не использовал числа, десятичные записи которых содержали некоторые цифры. Причем в разные годы обструкции подвергались разные комплекты цифр. В качестве начального номера в каждом году предыдущий руководитель брал минимальное неотрицательное число, не содержащее отвергнутых в данном году цифр. При нумерации каждого следующего документа, в тех случаях, когда следующий номер содержал отвергнутую цифру, это число просто пропускалось. И так до тех пор, пока очередное число не оказывалось свободным от нежелательных цифр. Например, если отвергались цифры 8, 7, 9, 5, 1, первые несколько документов этого года имели следующие номера: 0, 2, 3, 4, 6, 20, 22, 23, 24, 26, 30, 32, 33, ...

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

Формат ввода-вывода:

Программа Numbering читает с клавиатуры (стандартного устройства ввода) две непустые строки. В первой строке через пробел перечислены нелюбимые цифры (их общее количество от одной до восьми включительно). Во второй строке дан исходный номер искомого документа (не меньше нуля и не более 1,000,000,000).

Программа Numbering выводит на экран (стандартное устройство вывода) единственное число – номер запрошенного документа, т.е. порядковый номер документа, исходный номер которого указан во входном файле.

Пример входных и выходных данных

- - - - - - - - - - - - - - - - - - - - - - - - -

Гномоградусы (Gnomedegrees)

Гномы прекрасно знают, что «Математика – царица наук!» и поэтому уделяют этому предмету особое внимание. Самыми любимыми у них являются геометрические задачи с кругами.

Однако, обратите внимание, что единицей измерения угла у гномов являются не градусы или радианы, а некоторая величина – гномоградус. Причем, в зависимости от настроения, эта величина может изменяться! Определяется эта величина таким образом: задается число L – количество равных частей, на которые делится круг.

И вот гномам задали такую задачу. На круге есть N перегородок с известными углами, заданными в гномоградусах, причем число L, определяющее гномоградус, обязательно кратно количеству перегородок N. Необходимо определить минимальное количество перемещений перегородок, в результате которого круг будет разделен на равные части.

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

Формат ввода-вывода:

Программа Gnomedegrees читает с клавиатуры (стандартного устройства ввода) две непустые строки. В первой строке два целых числа L и N (L≤10⁹, N≤10³, L кратно N), а во второй N целых чисел через пробел a_i (0≤ a_i≤L-1) – углы, на которых находятся перегородки, в гномоградусах. Начало отсчета для каждого угла от вертикали (см. рисунок).

Программа Gnomedegrees выводит на экран (стандартное устройство вывода) единственное целое число: минимальное количество перемещений.

Пример входных и выходных данных