1. Завдання 4 (ФІНАЛЬНОГО) туру

 Завдання фінального туру NetOI-2024 

10 лютого 2024 р.

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

Технічні умови. Програма Fourpoints спочатку зчитує з клавіатури (стандартного пристрою введення) єдине натуральне число N (1≤N≤50000) – кількість наборів, що тестуються. Далі йдуть N рядків, кожен з яких містить координати чотирьох попарно різних точок X₁ Y₁ , X₂ Y₂ , X₃ Y_{3 ,} X₄ Y_{4 ,}  де розміщено станції. Усі координати – цілі числа, що не перевищують за абсолютною величиною 10000.  Програма виводить на екран (стандартний пристрій виведення) N рядків, які містять мінімальну сумарну відстань від координаційного центра до вказаних чотирьох станцій. Відповідь буде зарахована, якщо буде відрізнятися від правильної не більш ніж на 10^-5.

Приклад

Задача Triangles2024.    N цілочисельних точок (N ≤ 10³) задано на декартовій площині XOY своїми координатами X_i Y_i .Координати по модулю не перевищують 100000.   Необхідно знайти кількість різних прямокутних трикутників, які можна побудувати на цих точках, як на вершинах.
Технічні умови. Програма  Triangles2024 читає з пристрою стандартного введення число N, а далі N рядків по 2 цілих числа – координати точок  X_i Y_i Програма виводить на пристрій стандартного виведення єдине число – кількість прямокутних трикутників, побудованих на цих точках, як на вершинах.

Приклади

Задача Cravat2024. На урочистому відкритті XXVI Всеукраїнської комплексної олімпіади з математики, фізики та інформатики «Турнір Чемпіонів», яка відновиться (автор вірить!) після перемоги, перед учасниками і гостями збирається виступити N членів журі. Щоб показати єдність всіх представників журі,  було прийнято рішення одягнути на них краватки одного кольору. Всі краватки зберігаються в скрині, яка знаходиться в темній кімнаті, та кожна з краваток  має один з M кольорів. У кімнату можна увійти тільки один раз, вийняти зі скрині деяку кількість краваток і винести їх з кімнати. Потрібно визначити мінімальну кількість краваток, яку необхідно вийняти зі скрині, щоб серед них гарантовано було не менше N краваток одного кольору.  Ситуацію ускладнює те, що  оргкомітет ще не знає, скільки точно буде членів журі, але впевнений - щонайменше N₁ та щонайбільше N₂. Вам, як досвідченому програмісту, необхідно знайти шукану кількість для кожного N між N₁ та N₂. 

Технічні умови Програма Cravat2024 зчитує зі стандартного пристрою уведення два рядки. Перший рядок містить три цілих числа N₁, N₂ та M (1≤N₁, N₂≤10⁶, 1≤M≤10⁴, 0 ≤ N₂ - N₁ ≤ 10⁵). У другому рядку задано M чисел, кожне з яких означає кількість краваток відповідного кольору. Всі числа цілі, невід’ємні та не перевищують 10^9.

Програма повинна вивести на стандартний пристрій виведення рівно N₂ - N₁ + 1 число – мінімальну кількість краваток, яку необхідно вийняти із скрині для кожного N від N₁ до N₂. Якщо для заданого N гарантувати наявність N краваток одного кольору не можливо, необхідно вивести число −1.

Приклади

Задача Brackets2024. Послідовність дужок ‘(‘ та ‘)’ назвемо k-красивою, якщо вона відповідає таким правилам:

• () – k-красива послідовність;
• Якщо А₁,A₂,…,A_k – k-красиві послідовності, то  послідовність (А₁A₂…A_k) теж k-красива;
• Всі інші послідовності некрасиві.

Наприклад, (()()) 2-красива,   послідовність  ((())) 1-красива, а послідовності ()()(), (())() некрасиві. Вам відомо число k та послідовність дужок. Яку мінімальну кількість дужок необхідно додати в кінець цієї послідовності, щоб вона стала k-красивою?

Технічні умови. Програма Brackets2024 читає з пристрою стандартного введення з першого рядка натуральне число k (1≤N≤10), а з другого – послідовність дужок (не більше 10000 символів).    Програма виводить на пристрій стандартного виведення шукану кількість символів. Якщо отримати k-красиву послідовність неможливо, програма має вивести -1.

Приклади

Задача Eq2024. Молодий програміст Василь Наливайко вивчив 3 чи 4 мови програмування, купу бібліотек до кожної, зробив немало навчальних проєктів на різних курсах, пройшов неформальне, і вельми корисне  стажування у друзів, які працювали у відомій компанії «Galery  Production» і вирішив, що пора йти на інтерв’ю. Але сталося не так, як бажалося. Допоможіть Василю розв’язати задачу – інакше то його візьмуть, але зарплата не дуже…

Дано два числа n, m ≤ 10¹⁸. Потрібно дізнатись кількість пар натуральних  a, b, a≤n, b≤m таких, що рівняння a+x=(b+x)² має хоча б 1 цілочисельний розв’язок. Відповідь вивести по модулю 10⁹+7

Технічні умови. Програма Eq2024  читає з пристрою стандартного введення  в одному рядку числа n  та  m через пропуск, і виводить на пристрій стандартного виведення шукане число по модулю 10⁹+7

Приклад

Введення   Виведення 

3 2                 3 

Завдання підготували  К. Денисов, Г. Непомнящий,  М.Стречень,  Ю.Пасіхов