Задача 2. Кибербоулинг

Распределение баллов за решение задач (заочный тур)

ЖЕЛАЕМ УСПЕХОВ!

ЗАДАЧА 1. ТРАНСПОРТНЫЙ РОБОТ

Для обслуживания четырех станков, находящихся в цехе, используется автономный транспортный робот. В режиме ожидания он находится возле главного контейнера. По команде он должен обойти все станки, собрать обработанные детали, вернуться с ними к главному контейнеру и разгрузиться (рис. 1). Нельзя дважды за обход подходить к одному и тому же станку. Известны попарные расстояния между всеми станками, а также между станками и контейнером. Если обозначить местоположения станков как А ₁- - - А ₄, а местоположение контейнера через А ₀, то все расстояния можно записать в матрицу R размером 5 х 5: R (i, j) определяет расстояние между i –й и j –й точками (R (i, j) может быть не равно R (j, i)).

Задание. Требуется определить самый короткий путь обхода станков.

Замечание. Входные данные всегда таковы, что существует единственный минимальный путь.

INPUT.TXT. Входной файл содержит 5 х 5 матрицу целых чисел (R).

OUTPUT.TXT. Выходной файл должен содержать длину самого короткого пути, на следующей строке номера пунктов, разделенных символом «-». Первый и последний пункты всегда имеют номер 0.

ПРИМЕР.

Входной файл:

0 17 10 5 17

18 0 6 12 20

12 5 0 14 19

12 11 15 0 7

16 21 18 6 0

Выходной файл:

0-2-1-3-4-0

Рисунок 1 – Транспортный робот

ЗАДАЧА 2. КИБЕРБОУЛИНГ

Робот с искусственным интеллектом играет в кибербоулинг (рис. 2). Поле - коридор, расстояние между стенками которого 20 м. По центру коридора стоят кегли (40 шт.), расстояние между центрами кегль 10 м, их радиус равен R. Робот бросает шар радиуса R с начальной скоростью 2м/с, под углом α (от стенки коридора).

Задание: В какую кеглю попадёт шар? Кегли пронумерованы натуральными числами.