ЗАДАЧІ 1 ТУРУ ВСЕУКРАЇНСЬКОЇ ІНТЕРНЕТ-ОЛІМПІАДИ З ІНФОРМАТИКИ NETOI-2023
Завдання слід виконати до 1 грудня 2023 р.
Задача Candy2023. У Марини є N видів цукерок, i-го виду Ai штук. Марія хоче розділити кожен вид цукерок на купки по R цукерок. Проблема лише в тому, що не завжди це можна зробити без залишку, тому Марина хоче вибрати або таке R, що усі види діляться без проблем, або щоб у залишку були рівні купки. Серед усіх можливих R Марина хоче вибрати найбільше.
Технічні умови. Програма Candy2023 зчитує з клавіатури число N - кількість видів цукерок (3 ≤ N ≤ 100000). Після цього програма зчитує ще N натуральних чисел - кількості цукерок кожного виду. Жодне число не перевищує 10 9. Програма виводить на екран єдине число R - відповідь на задачу.
Приклади
Введення
5
7 11 7 207 15
Виведення
4
Пояснення: в єдиному прикладі з кожного виду залишаться купки по 3 цукерки.
Задача Population2023. На планеті Олімпії живуть гуманоїди N стАтей. Вони зробили Великий Перепис Населення (ВПН) і отримали результат - кількість гуманоїдів кожної статі a1,a2,…,aN. Сім’я на Олімпії складається з двох гуманоїдів різної статі. Щоб уникнути демографічної кризи, на Всеолімпійському Конгресі Майбутнього (ВКМ) вирішили, що всі сім’ї, що існували до ВКМ, необхідно скасувати, а натомість створити максимальну можливу кількість сімей. Допоможіть олімпійцям підрахувати, скільки сімей утвориться на Олімпії після виконання рішення ВКМ.
Технічні умови. Програма Population2023 читає з пристрою стандартного введення кількість стАтей гуманоїдів N (2≤N≤1000) і через пропуск N натуральних чисел a1,a2,…,aN, не більших 109 - кількість гуманоїдів кожної статі. Програма виводить на пристрій стандартного виведення шукану кількість сімей.
Приклад
Введення
3 1 2 4
Виведення 3
Задача Permutation2023. Герой олімпіад Василько отримав у подарунок перестановку N чисел a1,a2,…,aN. (у перестановці кожне з чисел 1, 2,…,N міститься рівно один раз) Він застосував її для набору чисел 1,2,…,N таким чином. Перше число (тобто 1) поставив на позицію a1, друге (тобто 2) - на a2, останнє (тобто N) - на aN. Наприклад, для перестановки 2 4 5 1 3 Василько матиме 4 1 5 2 3. Далі Василько повторює ці дії (i те число ставиться на ai позицію) для отриманого набору чисел. Так, з 4 1 5 2 3 вийде 2 4 3 1 5. Скільки дій знадобиться Васильку, щоб знову отримати 1, 2,…,N?
Технічні умови. Програма Permutation2023 читає з пристрою стандартного введення з першого рядка натуральне число N (1< N<=10), з другого – перестановку a1,a2,…,aN. Гарантується, що після кожної дії Василька порядок чисел у наборі змінюється. Програма виводить на пристрій стандартного виведення єдине шукане число. Якщо Василько не зможе отримати 1, 2,…,N, програма має вивести -1.
Приклад
Введення
5
2 4 5 1 3
Виведення
6
Коментар. Василько отримає такі набори
4 1 5 2 3
2 4 3 1 5
1 2 5 4 3
4 1 3 2 5
2 4 5 1 3
1 2 3 4 5
Задача Factor2023. Факторизацією натурального числа називається розклад цього числа на натуральні множники, більші за 1. Наприклад, 12=3*4. Знайдіть кількість різних факторизацій заданого числа.
Технічні умови. Програма Factor2023 читає з пристрою стандартного введення число N (2≤N≤109) і виводить на пристрій стандартного виведення кількість факторизацій числа N.
Приклади
Введення 12
Виведення 3
Введення 19
Виведення 0
Коментар. 12=3∙4=2∙6=2∙2∙3. 19 - просте число.
Задача brackets2023. Послідовність дужок ‘(‘ та ‘)’ назвемо красивою, якщо вона відповідає таким правилам:
- () – красива послідовність;
- Якщо А та В – красиві послідовності, то послідовність (АВ) теж красива;
- Всі інші послідовності некрасиві.
Наприклад, (()()) красива, а ((())), ()()(), (())() некрасиві. Знайдіть кількість красивих послідовностей ланцюжка дужок завдовжки N.
Технічні умови. Програма brackets2023 читає з пристрою стандартного введення натуральне число N(1≤N≤10000) і виводить на пристрій стандартного виведення шукану кількість красивих послідовностей за модулем 1000000007.
Приклади
Введення 10
Виведення 2
Введення 5
Виведення 0
Завдання підготували Г.Непомнящий, Ю.Пасіхов