Сайт підготовки до олімпіади з інформатики

Задача 1. Затори на дорогах (JAMMING)

Автомобільні затори трапляються усюди, навіть у нашому невеличкому містечку. Дороги у нас мають дві смуги в одному напрямку, а автомобілі є лише двох типів габаритів: легкові (у пробці займають квадрат 1х1, якщо за 1 взяти ширину смуги) та вантажні (у пробці займають місце 2х1 вздовж смуги).

Водії дуже дисципліновані у тому плані, що вони не стають поперек смуги, не займають чужу площу, але й не залишають вільних місць.

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

Формат вхідних даних:

Вхідний файл містить єдине число S (1<=S<=10000) – задана відстань.

Формат вихідних даних:

Єдиний рядок вихідного файла повинен містити відповідь – кількість розстановок тур.

Достеменно відомо, що кількість цифр у відповіді не перевищує 700.

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

Задача 2. Збирання мита (TALLAGE) -70 балів.

Король країни Аріїв завоював N міст на території сусідніх держав.

Тепер йому необхідно створити систему збирання мита з завойованих територій. Він хоче збудувати таку систему шляхів між цими містами, щоб до будь-якого міста можна було дістатися (можливо, через інші міста) зі столиці, але у воєнному стані на транспорт виділяється дуже незначна частина фінансів, тому сумарна вартість побудованих шляхів сполучення між містами має бути мінімальною.

Вхідні дані:

Перший рядок вхідного файлу містить натуральне число N – кількість міст у країні, а також цілі числа X та Y – координати столиці.

Наступні N рядків містять через проміжок координати X_i , Y_i завойованих міст.

Вихідні дані:

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

Наступні рядки мають містити у довільному порядку список побудованих доріг у форматі:

<номер міста> => <номер міста>

При цьому столицю позначте номером 0.

Якщо відповідей декілька, виведіть одну довільну з них.

Приклади: