|
XIV Всеукраинская олимпиада по информатике (г. Одесса, март 2001г.) Первый тур
Треугольник задан на плоскости координатами своих вершин: (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. Строка и слова состоят из символов 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 – стоимость прокладки линии электроснабжения (1 Ј Ci Ј 300) от школы Ai до школы Bi (i=1,2,…,N). Пример входного файла 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
|
