Музичне шоу (Fixshow)

Оскільки Дім Дімич у черговий раз забув привітати бабусю з днем народження, він вирішив влаштувати для неї грандіозне музичне шоу. Для цього він знайшов рівний майданчик, у певних координатах якого розставив N найсучасніших електронних синтезаторів звуку. За задумом Дім Дімича, у деякі (можливо різні) моменти часу, вони почнуть видавати звуки (гарантовано різні), і звучання буде тривалим. Оскільки Дім Дімич хоче, щоб бабуся почула усі звуки якомога швидше, він вирішив знайти таку точку на майданчику, в якій вперше будуть чутися всі N звуків одночасно. Вирішити таку складну задачу самостійно він не зміг, а тому вдався до вашої допомоги.

Напишіть програму, яка обчислює координати точки і час, за який у ній звуки від усіх синтезаторів будуть чутися вперше, за умови, що звук поширюється тільки по повітрю зі швидкістю С, однаковою для усіх синтезаторів і напрямків. Іншими затримками (наприклад, кінцевою швидкістю поширення електричних сигналів) можна знехтувати.

Формат введення-виведення:

Програма fixshow зчитує з клавіатури (стандартного пристрою введення) спочатку число N (1<=N<=555) – кількість синтезаторів, потім N трійок чисел – координати синтезаторів на майданчику та час початку їх звучання і, нарешті, число С (0.1<=C<=1000) – швидкість розповсюдження звуку.

Значення координат не перевищують по модулю 10⁶ и не обов’язково цілі.

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

Результат зараховується, якщо час відрізняється від правильного не більше ніж на 10^-3 та у вказаний час у вказаній точці будуть чутися всі синтезатори.

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

Професор і помогатор (helper)

Незабаром у фіксіків очікуються престижні змагання з ремонту складного обладнання. Як відомо, для усунення особливо складних поломок обладнання фіксікі використовують помогатор, однак їм треба вміти користуватися досконало!

Професор Геній Євгенович винайшов нову експериментальну модель помогатора. І всі хочуть з нею терміново ознайомитися. Але ... у професора відпустка! Сімка почала вмовляти його дати помогатор учням і після довгих умовлянь професор погодився, але з деякими умовами:

- Геній Євгенович віддасть пристрій фіксіку X і хоче забрати його після відпустки у фіксіка Y.

- Кожен день помогатор повинен міняти свого власника.

Всього в класі навчається M учнів, а відпустка професора триває N днів.

Дім Дімичу відразу стало цікаво, які можуть бути варіанти «подорожі» помогатора по учнях, а Сімка – скільки всього існує таких варіантів.

Формат введення виведення:     

Програма helper зчитує з клавіатура (стандартного пристрою уведення) чотири цілих числа N, M (1 ≤ N, M ≤ 10⁹), X, Y (1 ≤ X, Y ≤ M).

Програма helper виводить на екран (стандартний пристрій виведення) єдине число – кількість можливих варіантів «подорожі» помогатора по учнях, за заданими правилами. Оскільки число може бути дуже великим, виведіть залишок від ділення цього числа на 10⁹ + 7.

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

Примітка. У першому прикладі існують такі варіанти «подорожі» помогатора по учнях:

1 2 1 3 2

1 2 3 1 2

1 3 1 3 2

1 3 2 3 2

1 3 2 1 2

Копір (copier)

Фіксікі настільки цікаві істоти, що неприємності Нулика під час його знайомства з копіром нічому їх не навчили. Тепер вже цілих N фіксіків забралися під кришку пристрою й опинилися у різних місцях скляної панелі ксерокса. Таємниця їх існування опинилася на межі розкриття, бо Лізонька, як завжди не вчасно, вирішила зробити копію якогось оголошення про загублені речі професора Генія Євгеновича. Щоб ніхто не зацікавився істотами на отриманій копії, потрібно одержати зображення, на якому рівно k фіксіків (точок) розташовано по діагоналі від низу до верху. Перелякані фіксікі зовсім розгубилися і недовго було початися паніці, якби Сімка не запропонувала такий вихід.

Представимо скануючу поверхню ксерокса координатною площиною з початком координат у лівому нижньому куту панелі. Тоді розташування фіксіків можна задати координатами точок (i, y_i), i ∈ [1..N], 0 ≤ y_i ≤ N ≤ 200000.

По команді fixup#i фіксік з номером i може переміститися на одну клітинку вверх, тобто з точки з координатами (i, y_i) у точку з координатами (i, y_i+1). Тепер потрібно за мінімальну кількість команд досягти того, щоб k фіксіків опинилися в точках з координатами (x_i, 1), (x_i+1, 2), ..., (x_i+k−1, k) (див. рисунок) або переконатися, що це неможливо.

Формат введення-виведення:

Програма copier спочатку зчитує з клавіатури (стандартного пристрою уведення) два цілих числа N та k (1 ≤ k ≤ N ≤ 200000). Потім зчитується N цілих чисел y₁, y₂, …, y_N – початкові положення фіксіків.

Програма copier виводить на екран (стандартний пристрій виведення) єдине число − мінімальну кількість команд, що потрібна для отримання необхідної конфігурації фіксіків, або «−1» (без лапок), якщо це зробити неможливо.

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

Фііксікі рахують (fixcount)

І знову Дім Дімич з Ваською готуються до олімпіади з усного рахунку. Тільки тепер їм необхідно розв’язувати приклади не тільки на додавання, але й на множення. Довелося залучити не тільки всіх фіксіків, а й професора Генія Євгенійовича для складання прикладів. Це було настільки обтяжливе заняття, що хлопцям почали давати одну й ту саму послідовність чисел, яку треба було спочатку додати, а потім перемножити. Виявилося, що у деяких випадках результат отримувався абсолютно однаковий! Наприклад, для послідовності чисел 1, 2 і 3 виконується властивість 1 + 2 + 3 = 1 * 2 * 3 = 6. Щоб трохи відволікти хлопців від рутинної роботи, Сімка запропонувала розв’язати обернену задачу: знайти число, яке можна представлено у вигляді набору натуральних чисел, сума і добуток яких дає одне й те саме число. І таке число знайшлося швидко - 4, адже 4 = 2 + 2 = 2 * 2. Через деякий час загальними зусиллями було знайдено число, у якого було РІВНО ДВА різних набори натуральних чисел {a₁, a₂, ..., a_p} і {b₁, b₂, ... b_q} (2 ≤ p, 2 ≤ q) таких, що

x = a₁ + a₂ + ... + a_p = b₁ + b₂ + ... + b_q = a₁ · a₂ · ... · a_p = b₁ · b₂ · ... · b_q

Та професор Геній Євгенович не зупинився на досягнутому! Він остаточно ускладнив задачу тим, що запропонував порахувати кількість цілих чисел на заданому інтервалі, для яких виконується вказана властивість, причому набори, що відрізняються тільки порядком елементів, потрібно вважати однаковими. Наприклад, 1+2+3 и 2+3+1 – однакові набори.

Формат введення-виведення:

Програма fixcount зчитує з клавіатури (стандартного пристрою введення) два цілих числа N та M (1≤N≤M≤10¹⁸).

Програма fixcount виводить на екран (стандартний пристрій виведення) єдине число – кількість цілих чисел x ∈ [N,M], ща мають вказану властивість.

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

Математика – цариця наук (fixolymp)

Перемога на олімпіаді з усного рахунку була здобута! Дім Дімич сидів і з подивом дивився на першу отриману медаль. В інтернеті він знайшов інформацію про те, що рівно через рік відбудуться дуже престижні змагання у місті Вінниці – XXV Всеукраїнський Турнір Чемпіонів. Треба готуватися. Але як?

І тут до нього прийшов на допомогу професор Геній Євгенович. Він пообіцяв регулярно давати Дім Дімичу завдання та постійно контролювати їх виконання. І ось перше завдання.

Дано два натуральних числа A і B. Треба знайти два натуральних числа X і Y такі, що

НОД(A, B) = НОД(X, Y )

НОК(A, B) = НОК(X, Y )

X <= Y

Y − X → min

Формат введення-виведення:

Програма fixolymp зчитує з клавіатури (стандартного пристрою введення) два цілих числа A та B (1 ≤ A,B ≤ 10⁹).

Програма fixolymp виводить на екран (стандартний пристрій виведення) два цілих числа, що задовольняють умові задачі.

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