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

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

> Олимпиадная задача, задача на графе
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 19
Пол: Мужской
Реальное имя: Евгений

Репутация: -  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 ситуаций. При этом время подсчитывается очевидным способом.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
 
 Ответить  Открыть новую тему 
Ответов(1 - 1)
сообщение
Сообщение #2


Новичок
*

Группа: Пользователи
Сообщений: 19
Пол: Мужской
Реальное имя: Евгений

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


Начал решать задачу (писать на Паскале)...
Чего-то уже написал, осталось сделать так, чтобы программа перебор делала...
Помогите, плиз! Исходник во вложенном файле (вместе с матрицой дорог)

СРОЧНО!


Прикрепленные файлы
Прикрепленный файл  Robots.zip ( 2.36 килобайт ) Кол-во скачиваний: 196
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

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

 





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