Штанга (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 виводить на екран (стандартний пристрій виведення) єдине ціле число: мінімальну кількість переміщень.

Приклад вхідних та вихідних даних