IPB
ЛогинПароль:

> 

Начальные контакты ТОЛЬКО через личку!!

> Олимпиадная задача по теме "Графы", или встреча роботов
сообщение
Сообщение #1





Группа: Пользователи
Сообщений: 1
Пол: Мужской

Репутация: -  0  +



Между N пунктами (N<=50) заданы дороги длиной A(i,j),где I,J-номера пунктов.Дороги проложены на разной высоте и пересекаются только в общих пунктах.В начальный момент времени из заданных пунктов начинают двигаться с постоянной скоростью M роботов(M=2 или 3),независимо меняя направление движения только в пунктах.Роботы управляются таким образом,чтобы минимизировать время до встречи всех роботов в одном месте.Скорость I-того робота может быть равна 1 или 2.Остановка роботов запрещена.
Задание:
Написать программу,которая:
1)при заданных N,M и сети дорог единичной длины ( все имеющиеся A(i,j)=1) определяет минимальное время , через которое может произойти встреча всех M роботов,при этом начальное положение роботов и скорость их движения известны.
2)Выполнить те же действия,что и в п.1,но только для различных значений A(i,j).
Примечание:В случае невозможности встречи всех M роботов в одном месте ни в какой момент времени в результате выполнения программы должно быть сформировано соответствующее сообщение.
Требование к вводу-выводу:
1)Все входные данные-целые неотрицательные числа,
2)при задании сети дорог должно быть указано количество дорог - K и пункты их начала и конца в виде пар(i,j).

Устное решение:
Для решения задачи важно понять, что встреча роботов может произойти либо в пункте, либо на дороге. В первом случае задача решается просто: необходимо последовательно строить множества пунктов для каждого робота, в которых они могут оказаться через время, равное 0.5,1,1.5,2,...Т. Это можно делать, используя очереди. В случае же встречи роботов на дороге легко понять, что непосредственно перед встречей все они должны были находится в следующих пунктах: 1. Либо в двух пунктах, связанных дорогой; 2. Либо в пунктах, из которых есть дороги в один и тот же пункт; 3. Либо в трех пунктах, образующих треугольник. Поэтому, после каждого целого такта времени, достаточно проверять, находятся ли роботы в одной из описанных 3 ситуаций. При этом время подсчитывается очевидным способом.

Вот такое чудо нужно к завтрашнему дню на Паскале, что скажете? Какова стоимость? dry.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

Сообщений в этой теме


 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 28.03.2024 21:07
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name