Завдання фінального туру NetOI-2024
10 лютого 2024 р.
Задача Fourpoints. У цьому році після успішного завершення літньої школи ініціативна група вирішила провести квест. Було прийняте рішення обладнати чотири станції і тепер потрібно визначити, де необхідно розташувати координаційний центр квесту. Єдиною вимогою для його розміщення є виконання такої умови: сумарна відстань від координаційного центра до кожної станції повинна бути мінімальною.
Технічні умови. Програма Fourpoints спочатку зчитує з клавіатури (стандартного пристрою введення) єдине натуральне число N (1≤N≤50000) – кількість наборів, що тестуються. Далі йдуть N рядків, кожен з яких містить координати чотирьох попарно різних точок X1 Y1 , X2 Y2 , X3 Y3 , X4 Y4 , де розміщено станції. Усі координати – цілі числа, що не перевищують за абсолютною величиною 10000. Програма виводить на екран (стандартний пристрій виведення) N рядків, які містять мінімальну сумарну відстань від координаційного центра до вказаних чотирьох станцій. Відповідь буде зарахована, якщо буде відрізнятися від правильної не більш ніж на 10-5.
Приклад
|
Введення |
Виведення |
|
2 0 0 0 1 0 2 0 3 0 0 1 1 0 1 1 0 |
4.0000000 2.8284271 |
Задача Triangles2024. N цілочисельних точок (N ≤ 103) задано на декартовій площині XOY своїми координатами Xi Yi .Координати по модулю не перевищують 100000. Необхідно знайти кількість різних прямокутних трикутників, які можна побудувати на цих точках, як на вершинах.
Технічні умови. Програма Triangles2024 читає з пристрою стандартного введення число N, а далі N рядків по 2 цілих числа – координати точок Xi Yi Програма виводить на пристрій стандартного виведення єдине число – кількість прямокутних трикутників, побудованих на цих точках, як на вершинах.
Приклади
|
Введення |
Виведення |
|
4 0 0 2 0 0 2 2 2 |
4 |
|
5 0 0 2 0 0 2 2 2 1 1 |
8 |
Задача Cravat2024. На урочистому відкритті XXVI Всеукраїнської комплексної олімпіади з математики, фізики та інформатики «Турнір Чемпіонів», яка відновиться (автор вірить!) після перемоги, перед учасниками і гостями збирається виступити N членів журі. Щоб показати єдність всіх представників журі, було прийнято рішення одягнути на них краватки одного кольору. Всі краватки зберігаються в скрині, яка знаходиться в темній кімнаті, та кожна з краваток має один з M кольорів. У кімнату можна увійти тільки один раз, вийняти зі скрині деяку кількість краваток і винести їх з кімнати. Потрібно визначити мінімальну кількість краваток, яку необхідно вийняти зі скрині, щоб серед них гарантовано було не менше N краваток одного кольору. Ситуацію ускладнює те, що оргкомітет ще не знає, скільки точно буде членів журі, але впевнений - щонайменше N1 та щонайбільше N2. Вам, як досвідченому програмісту, необхідно знайти шукану кількість для кожного N між N1 та N2.
Технічні умови Програма Cravat2024 зчитує зі стандартного пристрою уведення два рядки. Перший рядок містить три цілих числа N1, N2 та M (1≤N1, N2≤106, 1≤M≤104, 0 ≤ N2 - N1 ≤ 105). У другому рядку задано M чисел, кожне з яких означає кількість краваток відповідного кольору. Всі числа цілі, невід’ємні та не перевищують 109.
Програма повинна вивести на стандартний пристрій виведення рівно N2 - N1 + 1 число – мінімальну кількість краваток, яку необхідно вийняти із скрині для кожного N від N1 до N2. Якщо для заданого N гарантувати наявність N краваток одного кольору не можливо, необхідно вивести число −1.
Приклади
|
Введення |
Виведення |
|
3 5 3 4 5 6 |
7 10 13 |
|
5 6 5 6 6 6 6 6 |
21 26 |
Задача Brackets2024. Послідовність дужок ‘(‘ та ‘)’ назвемо k-красивою, якщо вона відповідає таким правилам:
- () – k-красива послідовність;
- Якщо А1,A2,…,Ak – k-красиві послідовності, то послідовність (А1A2…Ak) теж k-красива;
- Всі інші послідовності некрасиві.
Наприклад, (()()) 2-красива, послідовність ((())) 1-красива, а послідовності ()()(), (())() некрасиві. Вам відомо число k та послідовність дужок. Яку мінімальну кількість дужок необхідно додати в кінець цієї послідовності, щоб вона стала k-красивою?
Технічні умови. Програма Brackets2024 читає з пристрою стандартного введення з першого рядка натуральне число k (1≤N≤10), а з другого – послідовність дужок (не більше 10000 символів). Програма виводить на пристрій стандартного виведення шукану кількість символів. Якщо отримати k-красиву послідовність неможливо, програма має вивести -1.
Приклади
|
Введення |
Виведення |
|
2 (( |
4
|
|
1 ((( |
3 |
|
2 ()) |
-1
|
Задача Eq2024. Молодий програміст Василь Наливайко вивчив 3 чи 4 мови програмування, купу бібліотек до кожної, зробив немало навчальних проєктів на різних курсах, пройшов неформальне, і вельми корисне стажування у друзів, які працювали у відомій компанії «Galery Production» і вирішив, що пора йти на інтерв’ю. Але сталося не так, як бажалося. Допоможіть Василю розв’язати задачу – інакше то його візьмуть, але зарплата не дуже…
Дано два числа n, m ≤ 1018. Потрібно дізнатись кількість пар натуральних a, b, a≤n, b≤m таких, що рівняння a+x=(b+x)2 має хоча б 1 цілочисельний розв’язок. Відповідь вивести по модулю 109+7
Технічні умови. Програма Eq2024 читає з пристрою стандартного введення в одному рядку числа n та m через пропуск, і виводить на пристрій стандартного виведення шукане число по модулю 109+7
Приклад
Введення Виведення
3 2 3
Завдання підготували К. Денисов, Г. Непомнящий, М.Стречень, Ю.Пасіхов