2liga_final_2013

Всеукраїнська студентська олімпіада з програмування

ФІНАЛ. Харків

24-27 жовтня 2013

Задача A. Естафета.

Після Євро-2012 наші славетні земляки Котигорошко, Вернигора та Пан Коцький знайшли багато нових друзів по усьому світу. Цього року вони вирішили трішечки помандрувати і завітати до своїх нових друзів у різних країнах.

Їхня перша подорож була до Квіткового міста, де жили коротуни Незнайко та його друзі. Саме в той день, коли наші герої приїхали до міста, там проходила спортивна естафета на велосипедах, які сконструювали Гвинтик та Шпунтик. Особливістю цих велосипедів було те, що кожний з них міг їхати тільки з однією швидкістю, але швидкості різних велосипедів могли відрізнятися.

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

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

1-й рядок: K – кількість етапів естафети ( 1 ≤ K ≤ 1 000). 2-й рядок: M1/N1 M2/N2 ...... MK/NK – швидкості коротунів на етапах естафети у вигляді простих дробів записаних

через пробіл. Mі , Nі – цілі числа (1 ≤ Mі , Nі ≤ 10).

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

M/N – шукана швидкість Пана Коцького у вигляді простого нескоротного дробу.

Приклад:

Всеукраїнська студентська олімпіада з програмування

ФІНАЛ. Харків

24-27 жовтня 2013

Задача B. Змагання з орієнтування

В той час, коли Пан Коцький приймав участь у велоперегонах – Котигорошко та Вернигора вирішили взяти участь у змаганнях зі спортивного орієнтування. На старті, що знаходився у точці з координатами (X0,Y0) вони отримали карту і координати наступної точки (X1,Y1). Діставшись до неї – отримали координати другої точки – (X2,Y2), і так до останньої (N–1) точки. З останнього пункту вони повернулися на старт і нанесли свій маршрут повністю на карту, Вернигора сказав: "Подивись Котигорошку, наш маршрут нагадує правильний невироджений N–кутник". "Та ні, відповів Котигорошко, – це не так". Допоможіть друзям у цьому питанні.

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

У першому рядку записано ціле число N (3 ≤ N ≤ 100) – кількість пунктів на маршруті.. У -тому з наступних N рядків через пробіл записані дійсні числа XI та YI (0 ≤ XI, YI ≤ 1) – координати -ї точки. Координати різних точок можуть збігатися, але гарантується, що існує хоча б одна пара точок на відстані не менше 0.3.

Координати задані з точністю не менше 10–10.

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

Якщо в результаті перевірки не вдалося побудувати вершини правильного N-кутника у порядку проходу, виведіть у єдиному рядку NO, в іншому випадку виведіть

YES.

Гарантується, що у разі негативної відповіді не можна змінити координати точок менше ніж на 10–5 так, щоб вони стали координатами вершин правильного N-кутника, записаними в порядку обходу.

Приклад:

Всеукраїнська студентська олімпіада з програмування

ФІНАЛ. Харків

24-27 жовтня 2013

Задача C. Корінь кубічного рівняння

Приїхавши до Італії, наші герої дізналися про математичні змагання, що проходили між вченими у епоху Відродження. Особливо їх зацікавила історія змагання між математиками Фіоре та Тарталья, сутність якого зводилася до знаходження коренів кубічного рівняння.

Будь ласка, і Ви напишіть програму, яка знаходить корінь кубічного рівняння

Ax3 + Bx2 + Cx + D = 0 (A≠0).

Відомо, що у цього рівняння є тільки один дійсний корінь. Необхідно його знайти.

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

У вхідному файлі через пробіл записані чотири цілих числа: A, B, C, D,

−1 000 ≤ A, B, C, D ≤ 1 000.

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

Виведіть єдиний корінь рівняння з точністю не менше ніж 10–5.

Приклад:

Всеукраїнська студентська олімпіада з програмування

ФІНАЛ. Харків

24-27 жовтня 2013

Задача D. Казино

З Італії Котигорошко та Пан Коцький заїхали у Монте-Карло (Вернигора у цей час поїхав подивитися боксерські поєдинки до Німеччини). Звісно у Монте -Карло ні Котигорошко ні Пан Коцький не могли не зайти до казино. Особливо їм сподобався один гральний апарат, який називали "Розлучена пара", що нагадував "однорукого бандита". Його відмінністю від інших подібних апаратів було те, що він мав N барабанів (2 ≤ N ≤ 100) і кожний барабан міг мати M різноманітних малюнків (2 ≤ M ≤ 10 000 000). В той же час загальна кількість комбінацій появи малюнків на барабанах, що могла виникнути на "Розлученій парі", не перевищувала 1015. Свою назву гральний апарат отримав від того, що виграшна комбінація появи малюнків вважалася такою, коли тільки на двох барабанах, що не розташовані поруч, випадали однакові малюнки. На всіх інших барабанах, при цьому повинні були з'явитися відмінні один від одного малюнки. Пана Коцького зацікавило питання – "Яка вірогідність появи виграшної комбінації для грального апарату "Розлучена пара"?". Допоможіть нашому герою знайти відповідь на це запитання. Результат повинен бути вирахуваний з D десятковими знаками без округлення (2 ≤ D ≤ 1 000).

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

Три цілих числа розділені пробілами: N M D.

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

Одне число – вірогідність появи виграшної комбінації малюнків на барабанах "Розлученої пари".

Приклад:

Всеукраїнська студентська олімпіада з програмування

ФІНАЛ. Харків

24-27 жовтня 2013

Задача E. Голова професора Інтегралова

З Монте-Карло Котигорошко та Пан Коцький полетіли літаком до Лондона, де їх вже чекав Вернигора. Поруч з нашими героями летів професор Інтегралов, який був запрошений на міжнародний симпозіум. Професор вирішив продемонструвати свою здатність швидко та безпомилково виконувати складні математичні обчислення.

"Допустимо, – сказав професор, – що у нас є N – деяке натуральне число. Спочатку обчислимо факторіал цього числа, тобто N!, а після цього обчислимо суму усіх цифр, що складають число N!. Якщо сума виявиться більшою за 9, треба знов обчислити суму вже для отриманого числа і цю процедуру повторювати до тих пір, поки не отримаємо число у діапазоні від 1 до 9. Зрозуміло?".

"Так" – відповів Котигорошко.

Ну а далі сталося диво. Яке б початкове число не називали Котигорошко та Пан Коцький, професор не моргнувши оком, тут же називав правильну відповідь – число від 1 до 9.

Спробуйте написати програму, яка б моделювала інтелектуальні здібності професора Інтегралова.

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

Перший рядок вхідного файлу містить єдине число N (1 ≤ N ≤ 109).

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

У вихідний файл виведіть одне єдине число яке повідомляв професор Інтегралов нашим героям.

Приклад:

Всеукраїнська студентська олімпіада з програмування

ФІНАЛ. Харків

24-27 жовтня 2013

Задача F. Накрити стіл до чаю

Перебуваючи у Лондоні, наші герої зайшли у гості до свого доброго знайомого містера Лана Нетворка. Час як раз наближався до п’яти і містер Нетворк запропонував Котигорошку та його друзям традиційного англійського чаю. Стіл у містера Нетворка був прямокутний, а ось усі скатертини геть квадратні. У Пана Коцького зразу ж виникло питання – якою найменшою за площею скатертиною можна повністю накрити стіл у містера Нетворка?

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

Вхідний файл складається з 4 рядків, в кожній з яких міститься по два дійсних числа – координати кутів стола містера Нетворка, що задаються в порядку обходу по контуру. Усі числа задані з точністю до двох знаків після коми і не перевищують за модулем 1 000.

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

У вихідний файл треба вивести найменшу площу квадратної скатертини містера Нетворка, яка повністю покриває прямокутний стіл з точністю не менше ніж 10-5.

Приклад:

Всеукраїнська студентська олімпіада з програмування

ФІНАЛ. Харків

24-27 жовтня 2013

Задача G. Поламаний свіч

Накривши стіл і ведучи приємну бесіду, наші герої розповіли містеру Нетворку про свою подорож світом. "Я бачу ви полюбляєте вирішувати цікаві задачі?" – сказав містер Нетворк – "Тоді тримайте ще одну з моєї виробничої практики".

"Якось я займався налаштуванням комп'ютерної мережі у фірмі де тоді працював. Фірма мала N комп'ютерів. Свіч, до якого були підключені усі комп’ютери, почав сильно збоїти, і тому не будь-які два комп'ютери могли зв'язатися один з одним. Крім того, якщо комп'ютер A обмінювався інформацією з комп'ютером B, то ніякі інші комп'ютери не могли у цей час обмінюватися інформацією ні з A, ні з B. Вам необхідно обчислити максимальну кількість комп'ютерів, які могли одночасно брати участь у процесі обміну інформацією" – закінчив свою розповідь містер Нетворк.

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

У першому рядку файлу задано ціле число N (1 ≤ N ≤ 18). Далі йдуть N рядків по N символів, причому символ -го рядка дорівнює 'Y', якщо -й і -й комп'ютери можуть обмінюватися інформацією, інакше він дорівнює 'N'. -й символ -го рядка завжди дорівнює 'N', крім того, матриця символів симетрична.

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

Виведіть максимальну кількість комп'ютерів, які можуть одночасно брати участь у процесі обміну інформацією.

Приклад:

Всеукраїнська студентська олімпіада з програмування

ФІНАЛ. Харків

24-27 жовтня 2013

Задача H. Шах королю

З Туманного Альбіону наші мандрівники попрямували до Індії, де були вражені чарівною красою древніх храмів. Саме у цій подорожі вони також зацікавилися історією появи гри у шахи і іноді вечорами разом вирішували різноманітні шахові задачі і придумували їх самі. Одного разу Пан Коцький запропонував друзям таку задачу. На шаховій дошці довільно

розташовані біла тура, чорний король та К інших фігур (K ≥ 0). Яку мінімальну кількість ходів N (N ≥ 0), треба зробити білою турою, щоб вона оголосила шах чорному королю?

Примітка. Тура може ходити по шаховому полю на будь-яку відстань по горизонталі чи вертикалі, за умови вільності клітинок. Шах королю оголошується, якщо тура і король знаходяться на одній вертикалі або горизонталі і між ними відсутні інші фігури. Горизонталі шахової дошки позначаються цифрами від 1 до 8, вертикалі – латинськими літерами від A до H.

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

1-й рядок: Розташування білої тури і чорного короля на шаховій дошці. 2-й рядок: Розташування інших фігур на шаховій дошці.

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

Одне ціле число - мінімальний номер ходу – N, яким біла тура може оголосити шах чорному королю і –1, якщо це зробити неможливо.

Приклад:

Всеукраїнська студентська олімпіада з програмування

ФІНАЛ. Харків

24-27 жовтня 2013

Задача I. Магараджа

Вивчаючи історію шахів наші герої дізналися, що існував варіант гри у якій була присутня особлива фігура – Магараджа, яка об'єднувала у собі можливості ферзя і коня. Тут уже Вернигора, з посмішкою на устах, запропонував друзям таку задачу. Яку мінімальну кількість ходів потрібно зробити Магараджі, щоб на прямокутній дошці розміром M × N (1 ≤ N,M ≤ 2 000 000 000) обійти усі клітинки та повернутися у початкове місце?

Примітка. Магараджа може ходити на будь-яку кількість клітинок по вертикалі, горизонталі та діагоналям, а також як кінь – на дві клітинки по горизонталі і на одну по вертикалі, чи навпаки – на одну клітинку по горизонталі і на дві по вертикалі.

Ходом вважається переміщення Магараджі з однієї клітини на іншу згідно з правилами.

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

1-й рядок два цілих числа N та M через пробіл – розміри дошки.

2-й рядок два цілих числа I та J через пробіл – початкова позиція Магараджі.

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

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

Приклад:

Всеукраїнська студентська олімпіада з програмування

ФІНАЛ. Харків

24-27 жовтня 2013

Задача J. Встигнути на поїзд

Після досить довгої подорожі Котигорошко з друзями повернулися на Україну і деякий час відпочивали. Але якось вранці у Котигорошка задзвонив телефон і знайомий голос Пана Коцького промуркотів: "Послухай Котику, я тут отримав нове запрошення до Бразилії, так що швидко збирайся і мерщій на поїзд, бо не встигнеш. Гора вже їде.". Відстань від будинку Котигорошка до вокзалу дорівнює D (0 < D ≤ 1 000 000). Між будинком і вокзалом було перепахане поле, яке неможливо було обминути, шириною H2. Від будинку до поля відстань дорівнює – H1, а від вокзалу до поля – H3, ( 0 ≤ H1,H2,H3 ≤1 000 000; D ≥ H1+H2+H3 > 0).

Швидкість, з якою може пересуватися Котигорошко за межами поля дорівнює

V1, а по полю – V2, (0 < V1, V2 ≤1 000).

За який мінімальний час Котигорошко може дістатися вокзалу?

Примітка. Пересуватися по полосі шириною 0 неможливо.

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

Шість дійсних чисел, розділених пробілами, з точністю до однієї десятої: H1, H2, H3, V1, V2, D.

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

Одне число – мінімальний час, за який Котигорошко може дістатися вокзалу з точністю 10–6.

Приклад: