Увага!
Під час залікових турів розв'язки дозволяється надсилати тільки один раз за вказаними адресами.

Вища ліга

Розв'язки приймаються за адресою mvi_7@rambler.ru до 22 грудня 2005 року включно.

Копію надіслати на адресу: tur4@oiuv.infocom.khmelnitskiy.ua

В темі листа слід вказати: ZOI_2005.

Питання, щодо умов задач приймаються за адресою mvi_7@rambler.ru до 15 грудня включно.

Завдання 1. Змій. (30 балів)

   У країні Змієландії відбуваються щорічні змагання з проходження лабіринту зміями. Причому лабіринт є ламаною, ланки якої паралельні осям координат, і будь-які дві з них можуть мати не більше однієї спільної точки. Виграє змія найбільшої довжини, яка зможе подолати лабіринт. Причому очевидно, що деякі змії не зможуть продовжити свій шлях, так як на заваді їм буде стояти своє ж тіло. Перша і кінцева точки змії можуть одночасно знаходитися в одній точці. Довжина змії повинна не перевищувати довжину лабіринту.
   Владислав захоплюється зміями і не міг не звернути увагу на ці змагання. За час до змагань завдяки своїм біологічним пізнанням хлопчик може виростити змія довільної довжини. Напишіть програму, яка визначить довжину змія, який потрібно виростити Владиславу, щоб гарантувати свій виграш в змаганнях.

   Формат вхідних даних: у єдиному рядку вхідного файлу міститься число N (0≤N≤4000) - кількість пунктів лабіринту, через які він побудований. Кожні два сусідні пункти з’єднані прямою, яка паралельна осям координат. В наступних N рядках містяться по два числа x і y – координати пунктів лабіринту у порядку обходу , які за абсолютною величиною не перевищують 10000.

   Формат вихідних даних: у єдиний рядок вихідного файлу виведіть єдине число – довжину змія з точністю до чотирьох знаків після коми.

Приклад введення і виведення:

Завдання 2 . Терези. (30 балів)

   Є терези і набір гир масою 1, 3, 9, 27, ..., 3^(n-1)кг, причому кожна гиря в єдиному екземплярі. На лівий важіль терезів кладеться предмет масою m кг (0≤m≤3^(n-1)). Потрібно розподілити гирі на терезах так, щоб був досягнутий баланс. Не вимагається використовувати всі гирі.

   Формат вхідних даних: у першому рядку файлу Weight.in - числа m і n (n≤20) (цілі невід’ємні), розділені символом "пробіл".

   Формат вихідних даних: у першому рядку файлу Weight.out - число m і маси гир на лівому важелі в порядку зростання. У другому рядку - маси гир на правому важелі терезів у порядку зростання.

Приклад введення і виведення:

Завдання 3. Б-дерево. (40 балів)

   Владислав дуже цікавиться програмуванням, а особливо різними структурами даних. Зараз він намагається опанувати Б-дерева. Б-Дерево – це дерево, кожна вершина якого має рівно одного предка (крім кореня, який їх немає зовсім) і n дітей. Тож Владислав намагався намалювати на папірчику Б-дерево. Щоб детальніше розібратися, Владислав намалював в корені число m. Потім для кожної вершини, в якій знаходилося деяке число більше одиниці, він домалював n дітей, причому кожне з них було цілим і їхня сума дорівнювала числу у вершині, яку він розглядав. Владислав також намагався, щоб різниця між максимальним і мінімальним намальованим числом була як можливо менша. В кінці дня, закінчивши цю складну і виснажливу роботу, Владислав намагався порахувати суму написаних чисел, але так як Б-дерево було досить великим, то він кожного разу збивався з рахунку, і в результаті він звернувся за допомогою до вас.

   Формат вхідних даних: у єдиному рядку вхідного файлу міститься два числа n (1≤n<2^31) і m (2≤m<2^31).

   Формат вхідних даних: у єдиний рядок вихідного файлу виведіть єдине число – суму написаних Владиславом чисел.

Приклад введення і виведення:

Пояснення :

Нижче зображено, намальоване Владиславом дерево.

Примітка.
Приклад листа четвертого туру учасника вищої ліги з кодом 005.

Кому: mvi_7@rambler.ru
Копія: tur4@oiuv.infocom.khmelnitskiy.ua
Тема: ZOI_2005
Зміст листа:
Прошу перевірити розв'язки задач четвертого туру.
Учасник вищої ліги з кодом 005. (Не можна підписувати листи прізвищами)
Вкладка: файли U005T4Z1.PAS, U005T4Z2.PAS, U005T4Z3.PAS                                 на початок

Перша ліга

Розв'язки приймаються за адресою mailto: vapnichny@rambler.ru до 22 грудня 2005 року включно.

Копія на адресу: tur4@oiuv.infocom.khmelnitskiy.ua

Тема листа: ZOI_2005.

Питання, щодо умов задач приймаються за адресою vapnichny@rambler.ru до 22 грудня включно.

Задача 1. «Подільність» (30 балів)

   Одна царська особа, познайомившись із двійковою системою і отримавши інтелектуальну насолоду від таблички множення у цій системі (таке буває), вирішила перевірити ознаки подільності. Перша думка: «З якого числа розпочати перевірку». Оскільки царство святкувало 31-річчя особи, то придворний математик порадив розпочати саме з цього числа (наша порада була б іншою, чи не так?). Але…свято є свято.

   Задано двійкове число. Перевірити його подільність на 31.

Вхідні дані: В єдиному рядку текстового файлу bin. in записане двійкове число.

Вихідні дані: У стандартний вихідний потік вивести «yes» у разі коли дане число ділиться на 31, або «no» в іншому випадку.

Приклад вхідних і вихідних даних:

Задача 2. Площа. (30 балів)

   Трикутник на площині задається цілочисельними координатами вершин. Для заданої точки Z(X;Y) визначити, чи належить вона трикутнику.

Вхідні дані: В першому рядку текстового файлу trukut.dat записанi через пропуск координати вершин: X1 Y1 X2 Y2 X3 Y3. У другому через пропуск координати т. Z : X Y.

Вихідні дані: В текстовий файл trukut.sol записати «yes» у разі коли т. Z (X;Y) належить трикутнику, або «no» в іншому випадку.

Приклад вхідних і вихідних файлів:

Задача 3. «Добровільна пожертва» (40 балів)

   У загадковій країні Труляля, після чергової кольорової революції, у боротьбі із корупцією ввели нові грошові купюри номіналом 1, 3, 9, 27, 81… Поки кольорові воюють із міфічними корупціонерами, шустрий бармен свої «старі» звички переніс на новий лад, назвавши чайові добровільною пожертвою. Ваша задача допомогти мандрівнику мінімізувати витрати, тобто заплатити за чеком і, не порушуючи спокій у країні, видати якнайменшу добровільну пожертву бармену. Обмінні пункти у країні Труляля видають тільки по одній купюрі одного номіналу і у кишені мандрівника всіх нових купюр рівно по одній. Інфляційні процеси ще дають можливість «відпочити» на суму в межах одного мільярда.

Вхідні дані: В перший рядок текстового файлу tugrik.in записана сума, яку потрібно заплатити, згідно чеку.

Вихідні дані: В єдиний рядок текстового файлу tugrik.sol записати суму, яку потрібно віддати бармену, врахувавши добровільну пожертву.

Приклад вхідних і вихідних файлів:

Примітка.

Кому: vapnichny@rambler.ru
Копія: tur4@oiuv.infocom.khmelnitskiy.ua
Тема: ZOI_2005
Зміст листа:
Прошу перевірити розв'язки задач четвертого туру.
Учасник першої ліги з кодом 005. (Не можна підписувати листи прізвищами)
Вкладка: файли U005T4Z1.PAS, U005T4Z2.PAS, U005T4Z3.PAS                                 на початок