| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Интересные и занимательные задачи по программированию > Распространение файла на всю сеть |
| Автор: pompei 13.12.2007, 06:52 | ||||||
| Такая задача: Суть задачи: имеется компьютерная сеть из N пронумерованных компьютеров, некоторые компьютеры соединены между собой. В сети нет двух компьютеров, которые бы не были соединены хотябы через промежуточные (условие "Ы"). На указанном компьютере есть файл. Один компьютер одновременно может копировать файл только на один другой компьютер, с которым соединён. Время копирования файла - 1 минута. Необходимо скопировать этот файл на все компьютеры сети за минимальное количество времени. Задержки между операциями копирования не учитывать. Входные данные: файл, в первой строчке которого содержиться два числа, разделённые пробелом: первое - количество компьютеров в сети, второе - номер компьютера, на котором содержиться файл изначально. Остальные строчки содержат по два числа, разделённых пробелом - эти пары чисел обозначают номера соединенных компьютеров. Известно что этот файл определяет сеть, удовлетворяющую условию "Ы". Нумерация компьютеров начинается с 1. Выходные данные: файл, в последней строчке число - общее количество минут. В остальных строчках содержаться тройки чисел разделённых пробелом. Первое число указывает минуту с начала процесса копирования (первая минута - 1, вторая минута - 2). Второе число указывает номер компьютера, с которого файл копируется. Третье число указывает номер компьютера, на который производиться копирование файла. Если, например, в третью минуту три пары компьютеров производят копирование, то файл должен содержать три строки, у которых первое число будет 3. Требуется: написать программу, которая по входному файлу получает выходной файл. ЗЫ. На олимпиаде было дано ограничение на максимальное количество компьютеров в сети (точно не помню, но кажеться 64). Нужно попытаться без этого ограничения. Пример: Имеется сеть (звёздочкой обозначен компьютер, где изначально находиться файл):
Входной файл:
Выходной файл:
|