1. Неземні огірки (автор Олександр Рудик)

Максимальна оцінка: 100 балів
Обмеження на час: 0,15 сек.
Обмеження на пам’ять: 32 MБ
Вхідний файл: cucumbers.in
Вихідний файл: cucumbers.out
Програма: cucumbers.*

Експедиція землян на далекій планеті наштовхнулася на рослину, зовні схожу на огірок. Рослина живе лише n років, після чого гине. Протягом j-го року свого життя рослина виділяє a_j спор, кожна з яких наступного року проростає (перетворюється на рослину) і виділяє a₁ спор. На другий рік свого життя рослина виділяє a₂ спор, на третій — a₃ спор і т.д.

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

Земляни виявили у рослині сполуку, що пригнічує ріст ракових клітин. Одразу після цього прокинулися вулкани планети і знищили усі живі рослини і всі спори, крім однієї.

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

Для транспортування рослин земляни використовують спеціальні контейнери — окремого типу для кожного року життя рослини. В один контейнер можна вкласти b_j рослин j-го року життя. Було вирішено забрати якомога більше рослин, заповнивши контейнери повністю. Частково заповнювати контейнери нераціонально, бо інакше рослини буде зіпсовано при транспортуванні.

Завдання
З’ясувати, скільки рослин кожного віку залишиться на планеті після відльоту землян.

Вхідні дані

Єдиний рядок файлу містить у вказаному порядку десяткові записи натуральних чисел: m, n, a_j при j = 1, 2, …, n, b_j при j = 1, 2, …, n. При цьому справджуються такі нерівності: m < 2⁶⁴, n ≤ 9, a_j < 2⁶⁴, НСК(b₁, b₂, …, b_n) < 2³². Тут НСК — найменше спільне кратне чисел, перелічених у дужках через кому. У 32% тестів m < 20. У 32% тестів 20 < m < 2000. У 36% тестів 2000 < m < 10¹⁸.

Вихідні дані
Єдиний рядок файлу містить кількості рослин, що залишаться на планеті після відльоту землян, у порядку зростання кількості років життя (від першого до n-го).

Приклади

Пояснення
В обох випадках мова йде про рослину з дворічним циклом життя, яка протягом першого року виділяє 3 спори, протягом другого року — 4 спори, а контейнери вміщують або по 5 рослин першого року життя, або по 6 рослин другого року життя. Стан системи для рослин з дворічним циклом можна описати трійкою чисел:

Для поданих прикладів маємо:

Для усіх станів, крім початкового (одразу після виверження):

• перше число є сумою добутків:
  • другого числа на 3;
  • третього числа на 4;
• друге число є першим числом попередньої трійки;
• третє число є другим числом попередньої трійки.

Першому тесту — 1-ий рік після виверження — відповідає (3,1,0).
Другому тесту — 3-ій рік після виверження — відповідає (51,13,3).

  2. Максимальний трикутник (автор Олександр Рибак)

Максимальна оцінка: 100 балів
Обмеження на час: 0,15 сек.
Обмеження на пам’ять: 32 MБ
Вхідний файл: triangle.in
Вихідний файл: triangle.out
Програма: triangle.*

У лісі вирішили зробити майданчик для пейнтболу. З певних причин його захотіли зробити трикутним, причому щоб у кожному його куті знаходилося дерево. Також бажано, щоб майданчик був якомога більшої площі.

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

Вхідні дані
Перший рядок містить натуральне число n (3 ≤ n ≤ 2000) – кількість дерев. У кожному з наступних n рядків через пробіл записано два цілі числа x_j, y_j, які є координатами дерева з номером j (j = 1, 2, ..., n). Всі числа x_j, y_j за модулем не перевищують 20000.

Вихідні дані
Файл має містити найбільшу можливу площу трикутника з вершинами у деяких (x_i, y_i), (x_j, y_j ), (x_k, y_k) з-поміж заданих n точок. Координати вершин цілі, тому відповідь буде цілою або матиме дробову частину 0,5. При виведенні використовувати десяткову крапку.

Приклади

Примітка. У тесті 2 всі точки розташовано на прямій, тому відповідний трикутник вироджуються у відрізок, площа якого 0.

3. Дивногори (автор Данило Мисак)

Максимальна оцінка: 100 балів
Обмеження на час: 0,17 сек.
Обмеження на пам’ять: 256 MБ
Вхідний файл: hiking.in
Вихідний файл: hiking.out
Програма: hiking.*

Дивногори славляться своєю природою та розмаїттям маршрутів для піших екскурсійних прогулянок. У містечку є кілька площ і доріг між ними. Кожна дорога має довжину 1 кілометр та сполучає між собою дві площі, дозволяючи рух між ними у довільному напрямку. Із кожної площі в будь-яку іншу можна дійти по дорогах принаймні в один спосіб. Дороги інколи проходять по мостах, і на півшляху між площами перейти з однієї дороги на іншу неможливо, навіть якщо дороги «перетинаються».

Доїхати в Дивногори з Києва та повернутися назад можна на автобусі, який зупиняється на деяких — але не на всіх — площах містечка. Петрик П’яточкін планує влаштувати собі пішу екскурсію. Нещодавно хлопець почав поглиблено вивчати інформатику, і тепер, на жаль, має не так багато часу. Тому Петрик хоче прокласти найкоротший (і, отже, найшвидший) маршрут між двома різними площами, де зупиняється автобус.

Завдання
Знаючи схему доріг Дивногір, допоможіть Петрику знайти довжину бажаного маршруту.

Вхідні дані
У першому рядку вхідного файлу вказано натуральні числа n, m та k — відповідно кількість площ і доріг Дивногір та кількість площ, на яких зупиняється автобус. Площі містечка занумеровано натуральними числами від 1 до n.

У наступних m рядках файлу перераховано по два різних числа — номери площ, сполучених відповідною дорогою. Дороги не повторюються.

В останньому рядку вхідного файлу у порядку зростання перераховано k чисел, що задають номери площ, на яких зупиняється автобус (3 ≤ k < n).

Кількість площ у Дивногорах не перевищує 2000. Додатково відомо, що у 30 % тестів кожна площа сполучена дорогами не більше ніж із двома іншими площами.

Вихідні дані
Вихідний файл має містити єдине число — довжину у кілометрах шуканого маршруту.

Приклади

Пояснення до прикладів
У першому прикладі схема доріг виглядає таким чином:

Сірим кольором виділено зупинки автобуса. Петрик може прогулятися від першої площі до третьої (або у зворотному напрямку) чи від шостої площі до восьмої (або у зворотному напрямку): обидва маршрути мають довжину 2 кілометри. Натомість відстань між третьою і шостою площею складає вже 3 кілометри, а довжина шляху між будь-якими іншими парами зупинок буде навіть більшою.

У другому прикладі Петрик вибере маршрут від другої до шостої площі (або зворотний): довжина цього маршруту складає 3 кілометри, а відстань від обох цих площ до п’ятої площі більша за цю відстань на кілометр.

4. Дільники (автор Олександр Рудик)

Максимальна оцінка: 100 балів
Обмеження на час: 1 сек.
Обмеження на пам’ять: 32 MБ
Вхідний файл: divisors.in
Вихідний файл: divisors.out
Програма: divisors.*

Завдання
Знайти усі натуральні числа, що кратні m, мають n натуральних дільників і не мають простих дільників, крім тих, які є дільниками m.

Примітка. Умова «... не мають простих дільників, крім тих, які є дільниками m» забезпечує скінченну кількість чисел у відповіді.

Вхідні дані

Єдиний рядок файлу містить десяткові записи натуральних чисел m і n: 1 < m < 2⁶⁴, 1 < n ≤ 64.

Вихідні дані
Єдиний рядок файлу містить десяткові записи шуканих чисел у порядку зростання. Якщо шуканих чисел немає, рядок містить 0. Вхідні дані такі, що всі числа вихідного файлу менші від 2⁶⁴. У 60% тестів числа вихідного файлу менші від 12 000.

Приклади

5. Мітки (автор Олександр Рудик)

Максимальна оцінка: 100 балів
Обмеження на час: 0,15 сек.
Обмеження на пам’ять: 32 MБ
Вхідний файл: marks.in
Вихідний файл: marks.out
Програма: marks.*

Завдання
Експедиція землян на далекій планеті наштовхнулася на цивілізацію, що опанувала повітроплавання. Постійна хмарність у висотних шарах атмосфери заважає орієнтуватися за сонцем чи зорями, а одноманітність рівнинного ландшафту — за особливостями рельєфу. Тому аборигени вирішили в окремих місцях створити мітки у вигляді сукупності n кругів, центри яких розташовано у вершинах правильного n-кутника при n > 2 або у кінцях відрізка при n = 2. Круги мають однакові радіуси й дотикаються. Кожний круг зафарбовано одним з k кольорів.

Потрібно з’ясувати, скільки різних міток такого вигляду можна утворити. Різних у тому розумінні, що вони виглядають по-різному незалежно від того, як їх розглядати згори. Інакше кажучи, якщо їх неможливо сумістити поворотом у площині.

Вхідні дані
Єдиний рядок файлу містить у вказаному порядку десяткові записи натуральних чисел n і k: 1 < n < 10 000, 1 < k ≤ 100.

Вихідні дані
Єдиний рядок файлу містить шукану кількість різних міток описаного вигляду. Вхідні дані гарантують, що це число не перевищує 10¹⁹/n. 50% балів можна набрати, розв’язавши задачу при n < 7, k < 7.

Приклади

Пояснення до прикладів
Занумеруємо кольори натуральними числами від 1 до k включно. Тоді довільне розфарбування кругів (довільну мітку) можна подати послідовністю довжини n, значення всіх членів якої лежить у діапазоні 1..k і яка перелічує кольори кругів у порядку обходу кола у певному напрямку. Наприклад, проти напряму руху годинникової стрілки, якщо дивитися згори. Дві такі послідовності задають однакові мітки тоді й лише тоді, коли одну можна отримати з іншої “розрізанням на дві частини і перестановкою закінчення на початок”. Нижче подано різні мітки у вигляді послідовностей 2-, 3- і 4-цифрових чисел для кожного з випадків:

• 11, 12, 22;
• 111, 222, 333, 112, 113, 221, 223, 331, 332, 123, 132;
• 1111, 2222, 1112, 2221, 1122, 1212.

6. Інкасація (автор Юрій Знов'як)

Максимальна оцінка: 100 балів
Обмеження на час: 0,5 сек.
Обмеження на пам’ять: 128 MБ
Вхідний файл: cash.in
Вихідний файл: cash.out
Програма: cash.*

В кінці зміни в касі Вашої фірми назбиралось рівно N банкнот. На жаль, конкурентам вдалось підсунути одну фальшиву банкноту. Вам потрібно знайти саме цю фальшиву банкноту, бо це дозволить дізнатися, хто саме приніс фальшивку.

Всі традиційні способи виявити фальшивку не спрацювали. Залишився єдиний спосіб перевірити банкноти — здати їх у банк, який має супер-секретний спосіб перевірки банкнот. За один раз у банк можна передати довільний набір з наявних банкнот. Якщо всі з переданих банкнот були справжніми, то гроші зразу зараховують на рахунок фірми. Вся така процедура займає рівно A секунд. Якщо серед переданих банкнот була фальшива, то всі банкноти повернуть назад і повідомлять, що серед набору була фальшива банкнота. Але не повідомлять, яка саме. Бо метод перевірки — супер-секретний. У цьому випадку вся процедура займе рівно B секунд. Якщо ви подасте банку на перевірку фальшиву банкноту більше ніж K разів, то банк щось запідозрить, а вам доведеться давати пояснення у різних установах. Це займе настільки багато часу, що цього не можна допустити в жодному разі.

Завдання
Визначити найменший час, необхідний для виявлення фальшивої банкноти.

Вхідні дані
Єдиний рядок файлу містить натуральні числа: N, A, B, K. Відомо, що N ≤ 10⁶, K ≤ 10, A < B ≤ 10⁶.

Вихідні дані
Файл має містити десятковий запис натурального числа — найменшої кількості секунд, протягом яких гарантовано можна виявити фальшиву банкноту.

Приклади

Пояснення до прикладів

У першому тесті в кінці зміни в касі була лише одна банкнота. І відомо, що є одна фальшива банкнота. Тому можна обійтись без інкасації.

У другому тесті в касі — 2 банкноти, одна з них фальшива. Оптимальним планом буде здати довільну банкноту. Якщо вона виявиться фальшивою, то це стане відомо за 3600 сек. Інакше (якщо здана банкнота справжня) нездана банкнота фальшива, що стане відомо за 300 сек. У найгіршому (першому) випадку потрібно 3600 сек.

У третьому тесті в касі — 10 банкнот, серед яких рівно одна фальшива. Оптимальною стратегією буде здавати по одній банкноті до тих пір, поки не здамо фальшиву. В найгіршому випадку потрібно 9 інкасацій за умови, що фальшиву банкноту буде знайдено лише після останньої спроби: 300∙8 + 3600 = 6000 (сек.).

У п’ятому тесті в касі — 20 банкнот. Але цього разу принести до банку фальшиву банкноту можна один раз (K = 1). Зауважимо: якщо принести на перевірку більше ніж одну банкноту і виявиться, що серед них є фальшива, то буде неможливо встановити, яка саме з них є фальшивою. Неможливо, бо не можна ризикувати принести у банк фальшиву банкноту ще раз. Якщо носити по одній банкноті, то нам у найгіршому випадку потрібно буде 19 інкасацій, з яких ми лише після останньої дізнаємося, яка з банкнот є фальшивою. У цьому випадку знадобиться 18∙10 + 100 = 280 (сек.).