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₁, a₂, …, b_n) < 2³². Тут НСК — найменше спільне кратне чисел, перелічених у дужках через кому.

У 32% тестів m < 20. У 32% тестів 20 < m < 2000. У 36% тестів 2000 < m < 10¹⁸.

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

Приклади

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

(кількість спор, кількість рослин 1-го року життя, кількість рослин 2-го року життя).

Для поданих прикладів маємо: (1,0.0) → (3,1,0) → (13,3,1) → (51,13,3) → …

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

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

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

2. Дільники

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

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

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

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

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

Приклади

3. Інкасація

Максимальна оцінка: 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 (сек.).