`Всеукраїнський центр проведення олімпіад в мережі Інтернет
  1. Условия 4 тура

Тур 4

27.01.98-15.02.99г.

По предварительному решению оргкомитета этот тур будет последним!!!!

Задача 4A

"Как лететь"

Одному человеку необходимо срочно перелететь из города A в город B возможно через какие-то другие города. У него имеется
расписание рейсов из одного города в другой. Как ему нужно
лететь, чтобы приле как можно раньше в город В?

Ваша программа должна считать исходные данные из файла
TASK4A.DAT. В первой строке этого файла находятся количество
городов N (1<N<=50), во второй код города A, в третьей -код
города B(1<=A, B <=50). В четвертой строке находится число K -
количество рейсов в расписании (1<=K<=2500). В следующих K
строках находится по шесть целых чисел: код города вылета, код
города посадки, время вылета, время посадки (часы и минуты).
Считается, что человек прибыл в аэропорт города А ровно в
полночь.

Ваша программа должна решить задачу и записать в первую
строку файла TASK4A,SOL количество используемых рейсов, во вторую
строку время прибытия в город В. В следующие строки записать коды
городов, составляющие маршрут перелета, начиная с кода города A и
кончая кодом города B. Если перелететь из города А в город В
невозможно, то выходной файл должен содержать в первой строке xbr> число 0.
Примеры входных и выходных данных
TASK4A.DAT
10
3
4
2
1 6 13 20 15 50
3 4 11 00 12 15
TASK4A.SOL
1
12 15
3
4

Максимальное количество баллов 30

Задача 4B

"Ненадежная сеть "

Некоторая фирма придумала хитрый способ очень быстрой
передачи сообщения между компьютерами. Было бы очень хорошо, но
один ученый утверждает, что, после опредленного количества
передач сообщения между компьютерами, первоначальное сообщение
искажается. Его объяснения этого были настолько туманными, что
никто ничего не понял и решили проверить это предположение
следующим образом. Несколько компьютеров соединяют друг с другом,
после чего одному из компьютеров вводится сообщение. Он посылает
это сообщение какому-то компьютеру, который соединен с ним. Как
только какой-то компьютер получает сообщение он его тут же
посылает другому компьютеру и т. д. После того, как сообщение
было послано ровно N раз, компьютер, на который пришло последний
(N-ый) раз сообщение выдает его на экран для того, чтобы его
сравнить с введенным сообщением. Возникает вопрос на каких
компьютерах нужно ожидать сообщение.

Ваша программа должна считать исходные данные из файла
TASK4B.DAT. В первой строке этого файла находится число M -
количество компьютеров соединенных в сеть (1<M<=100). Во второй
строке - S номер компьютера, в который вводится сообщение. На
третьей строке N количество пересылок (1<=N<2000000000 ). Далее
следует M строк по M чисел в каждой. Если в i-ой строке на j-ом
месте находится 1- то с компьютера i можно послать сообщение на
компьютер j, если 0 - то нельзя.

Ваша программа должна решить задачу и записать в первую
строку выходного файла TASK4B.SOL число компьютеров, на которых
следует ожмдать сообщение, и в следующих строках записать номера
всех этих компьютеров. Номера компьютеров должны располагаться в
возрастающем порядке.

Примечание: связь между компьютерами односторонняя, т.е.
если можно послать сообщение с компьютера i на компьютер j, то
нет гарантии, что с компьютера j можно послать сообщение на
компьютер i; с любого компьютера можно послать куда-нибудь
сообщение.

Примеры входных и выходных данных:
TASK4B.DAT
4
2
3
0 1 0 0
0 0 1 0
0 0 0 1
1 0 0 1
TASK4B.SOL
2
1
4
Максимальное количество баллов 30.

Задача 4C

"Караван"
Географическая карта местности задана квадратной сеткой определенного масштаба. В узлах сетки известна высота над уровнем
моря. Между соседними узлами высота изменяется плавно. Караван
перемещается только по линиям сетки. (Перемещение по диагонали
запрещается). Путь между двумя соседними точками с углом наклона
больше 45 градусов считается непроходимым.

Провести караван из точки А(X1,Y1) в точку B(X2,Y2) по
пути с наименьшим перепадом высоты или сообщить об отсутствии
решения.

Примечание: Перепадом высот на маршруте называется
разность высот между самой высокой и самой низкой точками
маршрута.

Ваша программа должна считать входные данные из файла
TASK4С.DAT. В первой строке этого файла находится число M
(1<M<=100)- количество узлов по горизонтали и вертикали.
Последующие М строк содержат каждая по M действительных чисел -
высоту над уровнем моря очередного узла. Последняя строка
содержит четыре числа - координаты точек А(X1,Y1) и B(X2,Y2).

Ваша программа должна решить задачу и записать в файл
TASK4C.SOL количество точек на карте, составляющее найденный
маршрут в первой строке. Перепад высот найденного маршрута во
второй строке. И координаты точек маршрута в последующих строках.
Если провести караван невозможно, в первой строке файла надо
записать число 0.

Примеры входных и выходных файлов:
TASK4С.DAT
4
1.4 1.9 2.2 2.5
0 5 1.0 1.6 2.0
1.2 2.0 1.2 2.1
1.0 0.1 5.1 1.3
1 1 4 4
TASK4С.SOL
7
0.9
1 1
1 2
1 3
2 3
2 4
3 4
4 4
Примечание
Координаты узлов стандартны в таком порядке: номер
строки (сверху вниз), номер столбца (слева направо). Указанный в
примере маршрут может быть неоптимальным.
Расстояние между
соседними узлами равно 1.

Максимальное количество баллов 30.

Задача 4D

"Построй палиндром"


Дана строка S. Определить минимальное количество
символов, которые надо добавить к строке s, чтобы получился
палиндром (т.е. строка, которая одинаково читается как слева
направо, так и справа налево).

Ваша программа должна считать исходные данные из файла
TASK4D.DAT. В первой строке этого файла находится строка S (длина
строки <=125).

Ваша программа должна решить задачу и записать в первую
строку файла TASK4D.SOL количество добавляемых в строку символов.
В следующую строку этого файла записать получившуюся
строку-палиндром.


Примеры входных и выходных данных:
TASK4D.DAT
abcabc
TASK4D.SOL
3
acbacabca
Максимальное количество баллов 40.
 

Задача 4Е

"Многочлен"

Вычислить коэффициенты A[1], A[2], ...,A[n] многочлена P(x) =x^n + A[1]*x ^(n-1) +...+ A[n-1]*x + A[n] с заданными действительными корнями X[1], X[2], ..., X[n].
Ваша программа должна считать исходные данные из файла
TASK4E.DAT. В первой строке этого файла находится число n -
порядок многочлена(n<=50). В каждой из следующих n строк
находится по одному действительному числу корни многочлена X[1],
X[2], ..., X[n].
Ваша программа должна решить задачу и записать число А[1]
в первую строку, А[2] - во вторую, ...,А[n] в n-ую строку файла
TASK4E.SOL..

Примеры входных и выходных данных:
TASK4E.DAT
2
1.00
1.00
TASK4E.SOL
-2.00
1.00
Примечание: x^n означает " x в степени n ". Вычисления
производить с точностью до 0.001

Максимальное количество баллов 30.
 

 

Последий день отравкирешений 15 февраля 1999 года. Решения отправлять по адресу olymp@.pmg17.vstu.vinnica.ua

27 января1999 года Пасихов

© LIKT 1998-2024