Олімпіада з інформатики.

Завдання II етапу Всеукраїнської учнівської олімпіади з інформатики

(16 листопада  2014 р., ТНПУ ім. В. Гнатюка, корпус фізико-математичного факультету)

Задача 1.

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

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

Перший рядок вхідного файлу містить три числа: N - кількість населених пунктів (N є [1;10000] , M - кількість доріг. Наступні M рядки задають дороги парами цілих чисел P,Q , де P і Q – номери населених пунктів, які з'єднані дорогою.

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

У вихідний файл виведіть номер шуканого населеного пункту ( місто-центр). Наступні M рядки  задають дороги парами цілих чисел P,Q , де P і Q – номери населених пунктів , які з'єднані дорогою (з  P до  Q) .

Задача 2.

Учень, який живе у будинку біля дороги між зупинками «Вітамінна»  і  «Майдан» на відстані X (м) від «Вітамінна»,  повинен доїхати до зупинки «Школа». В напрямку від зупинки «Вітамінна» до «Майдан» і далі по дорозі до зупинки «Школа» кожен день проїжджають автобус зі швидкістю V1 км/год. і трамвай зі швидкістю V2 км/год. На зупинку «Майдан»   вони приїжджають одночасно в 8:00 ранку. Щоб не запізнитись до школи, учень повинен сісти на один з них. У який найпізніший час t повинен вийти з будинку учень, щоб встигнути виїхати на автобусі? на трамваї?  Учень ходить зі швидкістю 5 км/год., відстань між зупинками S (км). Час, який транспорт стоїть на зупинці, дуже малий, а тому учень повинен прибути на зупинку швидше, або одночасно  з транспортом. Склавши відповідний алгоритм допоможіть учневі прийняти правильне рішення (поспати як найдовше і не запізнитись на уроки в школу J).

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

В вхідному файлі задано числа  X ,S,V1, V2.

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

Вивести шуканий час t1, t2.

Задача 3

 Квадратне  поле розбито на N смуг по N квадратиків. Деякі квадратики пофарбовано у жовтий   колір, серед яких лівий верхній квадратик  та правий нижній квадратик. Черепашка, яка знаходиться в лівій верхній клітинці, мріє потрапити у праву нижню.

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

 Вхідний файл input.txt  містить:

N – ціле число, розміри поля,(N<=100). Таблиця розміром N x N зі значеннями 0 або 1 – структура поля: 1 – пофарбований квадратик; 0 – чистий квадратик.

 Вихідній файл output.txt містить одне ціле число – 0 – якщо між вказаними квадратиками немає жодної траєкторії; додатне число – мінімальна кількість кроків, якщо між вказаними квадратиками є хоча б один маршрут.