|
3 тур - з 31.10 по 06.11.2016
точка входу для відправлення розв'язків http://134.249.159.199//cgi-bin/new-client?contest_id=35
Задача 1. Мега реклама (20 балів)
Ім’я вхідного файлу: input.txt
Ім’я вхідного файлу: output.txt
Ліміт часу: 1с.
На дошці наклеєно декілька листів оголошень. Всі вони прямокутної форми. Деякі листи накладаються частково або повністю. Усі горизонтальні та вертикальні сторони строго взаємо паралельні. Листи, які частково накладаються утворюють многокутник.
Директор рекламного агентства для підрахунку вартості розміщених оголошень наказав менеджерам порахувати загальну суму периметрів усіх утворених таким чином геометричних фігур (прямокутників, многокутників). Зрозуміло, що, коли лист із оголошенням повністю перекривається іншим, то периметр першого ніде не враховується.
Вхідні дані
У першому рядку вхідного файлу записано число N - кількість прямокутників. В наступних N рядках записано числа x1 y1 x2 y2 - декартові координати нижнього лівого та правого верхнього кутів прямокутника. Всі координати - цілі числа що по модулю не перевищують 10000.
Вихідні дані
У вихідний файл потрібно записати суму периметрів утворених геометричних фігур (прямокутників, многокутників).
Приклад
|
Приклад вхідних даних
|
Приклад вихідних даних
|
|
7
-15 0 5 10
-5 8 20 25
15 -4 24 14
0 -6 16 4
2 15 10 22
30 10 36 20
34 0 40 16
|
228
|
Задача 2. Майже Ханойські вежі (100 балів)
Ім’я вхідного файлу: input.txt
Ім’я вхідного файлу: output.txt
Ліміт часу: 1с.
Ігрове поле являє собою послідовність із N колонок по Ki фішок в кожній. За один хід із колонки з номером Ni можна забрати та перемістити по m фішок у сусідню ліву та праву колонку. (2*m ≤ Ki) Із крайньої лівої та правої колонок дозволяється переміщати фішки тільки в одну з сусідніх відповідно. Визначте яку найменшу кількість дозволених ходів потрібно виконати, щоб у кожній колонці була рівна кількість фішок. Гарантується що СУММ(Ki)/N завжди ціле число.
Вхідні дані
Перший рядок вхідного файлу містить число N - кількість колонок. В наступному рядку записано Ki - кількості фішок в кожній із колонок. (i є [1:N]) (2≤N≤200) (0≤Ki≤2000)
Вихідні дані
Вихідний файл повинен містити одне число - мінімальну кількість дозволених ходів.
Приклад
|
Input.txt
|
Output.txt
|
|
5
5 2 4 8 16
|
7
|
Примітка
колонка 3 беремо по 2, колонка 2 беремо по 2, колонка 5 беремо 16, колонка 4 беремо по 13, колонка 3 беремо по 7,колонка 5 беремо 12, колонка 4 беремо по 6.
|
