Задача Coins2019. Як вам відомо, в Україні вилучено з обігу монети 1, 2 та 5 копійок. Ці монети приймаються до обміну. Вам необхідно визначити кількість способів подати на обмін суму в N копійок цими монетами.
Технічні умови. Програма Coins2019 читає з пристрою стандартного введення натуральне число N, не більше 105 і виводить на пристрій стандартного виведення шукану кількість способів.
Приклад
Введення 5
Виведення 4
Задача Population2023. На планеті Олімпії живуть гуманоїди N стАтей. Вони зробили Великий Перепис Населення (ВПН) і отримали результат - кількість гуманоїдів кожної статі a1,a2,…,aN. Сім’я на Олімпії складається з двох гуманоїдів різної статі. Щоб уникнути демографічної кризи, на Всеолімпійському Конгресі Майбутнього (ВКМ) вирішили, що всі сім’ї, що існували до ВКМ, необхідно скасувати, а натомість створити максимальну можливу кількість сімей. Допоможіть олімпійцям підрахувати, скільки сімей утвориться на Олімпії після виконання рішення ВКМ.
Технічні умови. Програма Population2023 читає з пристрою стандартного введення кількість стАтей гуманоїдів N (2≤N≤1000) і через пропуск N натуральних чисел a1,a2,…,aN, не більших 109 - кількість гуманоїдів кожної статі. Програма виводить на пристрій стандартного виведення шукану кількість сімей.
Приклад
Введення
3 1 2 4
Виведення 3
Задача Factor2023. Факторизацією натурального числа називається розклад цього числа на натуральні множники, більші за 1. Наприклад, 12=3*4. Знайдіть кількість різних факторизацій заданого числа.
Технічні умови. Програма Factor2023 читає з пристрою стандартного введення число N (2≤N≤109) і виводить на пристрій стандартного виведення кількість факторизацій числа N.
Приклади
Введення 12
Виведення 3
Введення 19
Виведення 0
Коментар. 12=3∙4=2∙6=2∙2∙3. 19 - просте число.
Задача Tetris2023. Є в достатній кількості прямокутні плитки двох типів - квадрати розміром 1 × 1 і прямокутники розміром 1 × 2. За допомогою цих плиток необхідно замостити доріжку розміром 2 × n, при цьому плитки не повинні накладатися одна на одну. Плитки дозволяється повертати. Вам необхідно підрахувати кількість способів замощення доріжки 2×n за допомогою наявних плиток .
Технічні умови. Програма Tetris2023 читає з пристрою стандартного введення єдине ціле число n - довжина доріжки (1≤ n ≤1018). Програма виводть на екран кількість способів замощення смуги за допомогою плиток вказаного виду. Відповідь запишіть за модулем (109 + 9)
Приклади
|
Введення |
Виведення |
|
2 |
7 |
|
3 |
22 |
Коментар
В першому прикладі n = 2, доріжка має розміри 2 × 2, і її можливо замостити наявними плитками 7 способами:
 |