|
XIV Всеукраїнська олімпіада з інформатики Перший тур
Трикутник задано на площині координатами своїх вершин : (X1,Y1), (X2,Y2), (X3,Y3). Знайти довжину L сторони квадрата мінімальної площі, в який можна помістити цей трикутник так, щоб всі вершини трикутника знаходились всередині квадрата або на його сторонах. Завдання Напишіть програму SQUARE яка за координатами вершин трикутника знаходить довжину L сторони квадрата мінімальної площі, в який можна помістити цей трикутник. L достатньо знайти з точністю 10-4. Вхідні дані Файл SQUARE.DAT містить в одному рядку дійсні числа X1 Y1 X2 Y2 X3 Y3, розділені пропусками, – координати вершин трикутника (-10000 Ј X1, Y1, X2, Y2, X3, Y3 Ј 10000). Приклад вхідного файлу 0.0 0.0 1.1 0.0 0.0 1.1 Вихідні дані Файл SQUARE.SOL повинен містити одне число - довжину L сторони шуканого квадрата. Приклад вихідного файлу 1.1
Щоб дістатись до джерела живої води, мандрівнику треба пройти через лабіринт. Не завжди існує шлях до джерела, але мандрівник може проходити крізь стіни, використовуючи магію. На жаль, мандрівник може використовувати магію тільки обмежену кількість разів, а до джерела треба дістатися якомога швидше. Лабіринт має форму квадрата, що складається з Nґ N квадратних клітин, в середині якого уздовж сторін клітин можуть бути розташовані стіни. В кожний момент часу мандрівник може знаходитись в одній і тільки в одній клітині лабіринту. Одним кроком вважається переміщення мандрівника в сусідню по горизонталі чи по вертикалі клітину. Мандрівник може K разів проходити крізь стіну і не може виходити за межі лабіринту. Завдання Написати програму MAZE, яка визначить мінімальну кількість кроків, за яку мандрівник може дістатись джерела з координатами (P, Q), почавши шлях в клітині з координатами (1, 1). Вхідні дані Вхідний текстовий файл MAZE.DAT в першому рядку містить числа N, K, P, Q (2Ј NЈ 200, 0Ј KЈ 250, 1Ј P,QЈ N). Наступні N-1 рядків містять по N цілих чисел — ознак наявності горизонтальних стін між клітинами. Наступні N рядків містять по N-1 цілих чисел — ознак наявності вертикальних стін між клітинами. 0 позначає відсутність стіни, 1 – присутність. Приклад вхідного файлу 3 1 2 3 0 1 0 1 0 1 0 0 0 Вихідні дані Єдиний рядок вихідного текстового файла MAZE.SOL має містити знайдену мінімальну кількість кроків, або число –1, якщо шлях знайти не вдалося. Приклад вихідного файлу 3
XIV Всеукраїнська олімпіада з інформатики Другий тур 1. Задача “Шифр” Задано символьний рядок S довжини N (0 Ј N Ј 100) та словник, що містить M слів (0 Ј M Ј 100), довжина кожного з яких не перебільшує N. Cлова словника і рядок S складаються з літер a, b, …, z. Завдання Складіть програму CIPHER, котра визначає найменшу кількість символів, яку треба викреслити із заданого рядка S, щоб результуючий рядок можна було подати як послідовність слів словника. Кількість використань кожного слова не обмежується. Вважається, що пустий рядок можна подати за допомогою слів будь-якого словника. Рядок у прикладі після викреслювання зайвих букв f і t набуде вигляду abachdsya (було зроблено два викреслювання: aba Вхідні дані В першому рядку вхідного файла CIPHER.DAT знаходяться два цілих числа N та M, відокремлених пропусками. У другому рядку знаходиться символьний рядок S. У кожному з наступних M рядків знаходиться слово словника. Приклад вхідного файлу 11 5 abafchtdsya aba a bach dsy zero Вихідні дані В єдиному рядку вихідного файлу CIPHER.SOL має знаходитись натуральне число – мінімальна кількість викреслювань, після яких зашифрований рядок можна подати у вигляді послідовності слів словника. Приклад вихідного файлу 2 2. Задача “Школи” З метою підготовки до проведення олімпіади з інформатики мер вирішив забезпечити надійним електропостачанням всі школи міста. Для цього потрібно провести лінію електропередач від альтернативного джерела електренергії "Майбуття" до однієї з шкіл (не має значення до якої), а також з'єднати лініями електропередач деякі школи між собою. Вважається, що школа має надійне електропостачання, якщо вона напряму з’єднана з "Майбуттям", або з однією з шкіл, яка має надійне електропостачання. Відома вартість з’єднань між деякими парами шкіл. Мер міста вирішив обрати одну з двох найекономніших схем електропостачання (вартість схеми дорівнює сумі вартостей з’єднань пар шкіл). Завдання Складіть програму SCHOOLS, яка обчислює вартість двох найекономічніших схем альтернативного енергопостачання шкіл. Вхідні дані У першому рядку вхідного файлу SCHOOLS.DAT розташовані два натуральних числа, відокремлених пропусками: N (3 Ј N Ј 100), кількість шкіл в місті, та M - кількість можливих з’єднань між ними. В кожному з наступних M рядків знаходяться по три числа: Ai, Bi, Ci, відокремлених пропусками, де Ci - вартість прокладання лінії електропостачання Приклад вхідних даних 5 8 1 3 75 3 4 51 2 4 19 3 2 95 2 5 42 5 4 31 1 2 9 3 5 66 Вихідні дані В єдиному рядку вихідного файлу SCHOOLS.SOL мають міститись два натуральних числа S1 та S2, відокремлених пропусками – дві найменші вартості схем (S1Ј S2). S1=S2 тільки тоді, коли існує декілька варіантів схем надійного електропостачання найменшої вартості. Приклад вихідних даних 110 121 |
