програмування в С++
Задачі 09.09.2011 (заняття 1) |
![]() |
![]() |
![]() |
Добавил(а) Administrator | ||||||||
09.09.11 13:04 | ||||||||
Задача 1. Затори на дорогах (JAMMING) Автомобільні затори трапляються усюди, навіть у нашому невеличкому містечку. Дороги у нас мають дві смуги в одному напрямку, а автомобілі є лише двох типів габаритів: легкові (у пробці займають квадрат 1х1, якщо за 1 взяти ширину смуги) та вантажні (у пробці займають місце 2х1 вздовж смуги). Водії дуже дисципліновані у тому плані, що вони не стають поперек смуги, не займають чужу площу, але й не залишають вільних місць. Визначте, скільки існує різних за послідовністю типів машин (легкова - вантажна) заторів між мерією міста та моїм будинком, якщо вони на одній вулиці, а відстань між ними S. Формат вхідних даних: Вхідний файл містить єдине число S (1<=S<=10000) – задана відстань. Формат вихідних даних: Єдиний рядок вихідного файла повинен містити відповідь – кількість розстановок тур. Достеменно відомо, що кількість цифр у відповіді не перевищує 700. Приклад вхідних та вихідних даних:
Задача 2. Збирання мита (TALLAGE) -70 балів. Король країни Аріїв завоював N міст на території сусідніх держав. Тепер йому необхідно створити систему збирання мита з завойованих територій. Він хоче збудувати таку систему шляхів між цими містами, щоб до будь-якого міста можна було дістатися (можливо, через інші міста) зі столиці, але у воєнному стані на транспорт виділяється дуже незначна частина фінансів, тому сумарна вартість побудованих шляхів сполучення між містами має бути мінімальною. Вхідні дані: Перший рядок вхідного файлу містить натуральне число N – кількість міст у країні, а також цілі числа X та Y – координати столиці. Наступні N рядків містять через проміжок координати Xi , Yi завойованих міст. Вихідні дані: Перший рядок має містити дійсне число з трьома знаками після коми – сумарну вартість побудованих доріг. Вважайте, що вартість одиниці довжини дороги дорівнює одній умовній одиниці. Наступні рядки мають містити у довільному порядку список побудованих доріг у форматі: <номер міста> => <номер міста> При цьому столицю позначте номером 0. Якщо відповідей декілька, виведіть одну довільну з них. Приклади:
|
||||||||
Последнее обновление 09.09.11 13:08 |