Задача Fourpoints.
У цьому році після успішного завершення Турніру Чемпіонів ініціативна група вирішила провести квест. Було прийняте рішення обладнати чотири станції і тепер потрібно визначити, де необхідно розташувати координаційний центр квесту. Єдиною вимогою для його розміщення є виконання такої умови: сумарна відстань від координаційного центра до кожної станції повинна бути мінімальною.
Технічні умови
Програма Fourpoints спочатку зчитує з клавіатури (стандартного пристрою введення) єдине натуральне число N (1≤N≤50000) – кількість наборів, що тестуються. Далі йдуть N рядків, кожен з яких містить координати чотирьох попарно різних точок, де розміщено станції. Усі координати – цілі числа, що не перевищують за абсолютною величиною 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 |
- - - - - - - - - - - - - - - - - - - - - - - - - - - -
Задача Regexp
У вас є деякий текст S - послідовність маленьких літер латинського алфавіту. Вам необхідно знайти у цьому тексті кількість підрядків, які відповідають патерну, тобто шаблону.
Патерни у нас бувають лише вигляду “A*B” (замість A і B мають бути задані маленькі символи латиниці). Цей патерн означає наступне:
- рядок починається з символу A і закінчується символом B;
- довжина підрядка, що відповідає паттерну, не враховуючи А і В, ділиться націло на K.
Наприклад, якщо маємо патерн e*s та k=2, то рядки “es”, “eggs”, “errors”, “ends” підходять під цей патерн, а ось рядки “elixirs”, “posix” або “regexp” - не підходять.
Технічні умови
Програма Regexp читає з стандартного пристрою введення (клавіатури) рядок S - заданий текст, що складається лише з малих символів латиниці, довжина якого не перевищує 100 000. З наступного рядка програма має зчитати патерн – рівно три символи, У останньому рядку міститься єдине натуральне число К, що не перевищує 100 000.
Програма виводить на стандартний пристрій виведення (екран) єдине число – шукану величину.
Приклади
|
Введення |
Виведення |
|
abacaba a*a 1 |
6 |
|
ofoofooof o*f 3 |
4 |
- - - - - - - - - - - - - - - - - - - - - - - - - - - -
Задача Glassroom.
На уроці фізичного практикуму Василю необхідно побудувати конструкцію у вигляді прямокутника, де всі стінки є дзеркалами. У всіх чотирьох кутках конструкції знаходяться маленькі отвори, через які може проходити світло. Потрібно побудувати прямокутник такого розміру, щоб коли в його лівий нижній куток посвітити лазером під кутом 45 градусів, промінь лазера вийшов з правого нижнього кутка конструкції (дивись рисунок).
Василю дано N комплектів дзеркальних стінок. Кожен з них складається з двох дзеркал однакової довжини. Для побудови прямокутника необхідно використовувати рівно два комплекти. Яку максимальну кількість прямокутників можна побудувати з заданих комплектів одночасно, щоб виконувалися умови лабораторної.
Технічні умови
Програма Glassroom вводить зі стандартного пристрою введення (клавіатури) парне число N (2≤ N ≤107), після чого зчитує N натуральних чисел xi (1≤ xi ≤109) – довжини дзеркал відповідного комплекту. Усі числа розділені пропусками.
Програма виводить на стандартний пристрій виведення (екран) єдине ціле число – максимальну кількість прямокутників, що задовольняють умовам задачі.
Приклад
|
Введення |
Виведення |
|
6 2 2 3 4 6 10 |
2 |
- - - - - - - - - - - - - - - - - - - - - - - - - - - -
Задача Puzzle2019. Ігрове поле являє собою прямокутник з клітинок (5 рядків, 4 стовпчики), на якому розміщені плитки. Можливі розміри плиток - 1*1, 2*2, 1*2 та 2*1. Відомо, що плитка 2*2 єдина. Рівно дві клітинки вільні, плитки не можуть накладатись одна на одну та виходити за межі поля. За один хід можна перемістити одну плитку на одну клітинку по горизонталі або вертикалі. За яку найменшу кількість ходів можна отримати позицію, в якій клітинки (1,2) і (1,3) покриватимуться плиткою 2*2?
Технічні умови. Програма читає з стандартного пристрою введення 5 рядків по 4 цілих розділених пропуском числа в кожному рядку – початкову позицію. 0 – порожня клітинка, 1 – плитка 1*1, 2 – належить плитці 1*2, 3 – належить плитці 2*1, 4 – належить плитці 2*2. Програма виводить на пристрій стандартного виведення мінімальну кількість ходів. Гарантовано, що плитка 2*2 не покриває одночасно клітинки (1,2) і (1,3). Якщо перемістити плитку 2*2 згідно умови неможливо, програма виводить -1.
Приклад
Введення
1 1 0 1
1 4 4 1
1 4 4 1
1 1 1 3
2 2 0 3
Виведення
7
Коментар. Приклад відповідає позиції на малюнку.