ВСЕ ОТЛИЧНО
Информация о работе
Подробнее о работе
Timus Online Judge 1806. Мобильные телеграфы
- 1 страниц
- 2022 год
- 0 просмотров
- 0 покупок
Гарантия сервиса Автор24
Уникальность не ниже 50%
Фрагменты работ
1806. Мобильные телеграфы
Ограничение времени: 3.0 секунды
Ограничение памяти: 256 МБ
Каждому бойцу 25-й стрелковой дивизии выдали новейшее средство связи — мобильный телеграф. С его помощью можно отправлять телеграммы командованию и боевым товарищам прямо на поле битвы. К сожалению, конструкция телеграфов ещё далека от совершенства — передавать сообщения можно только между некоторыми парами телеграфов.
Каждому устройству присвоен уникальный номер — строка из десяти десятичных цифр. С телеграфа a можно отправить сообщение на телеграф b только в том случае, если из номера a можно получить номер b, изменив в нём ровно одну цифру либо поменяв в нём две цифры местами. Время передачи сообщения с телеграфа a на телеграф b зависит от длины наибольшего общего префикса их номеров — чем больше его длина, тем быстрее передаётся сообщение.
Во время очередного сражения Анка из своей хорошо замаскированной позиции увидела небольшую группу белых, пытающуюся обойти обороняющихся красноармейцев с тыла. Какое минимальное время понадобится на доставку этой информации от Анки до Чапаева по телеграфу, возможно, с помощью других красноармейцев?
Исходные данные
В первой строке записано целое число n (2 ≤ n ≤ 50000) — количество бойцов в дивизии. Во второй строке через пробел в порядке невозрастания записаны десять целых чисел в пределах от 1 до 10000 — время передачи сообщения с одного телеграфа на другой при длине общего префикса их номеров, равной нулю, единице, двум, …, девяти. Далее идут n строк, содержащие номера телеграфов, выданных бойцам дивизии. Номер телеграфа Анки указан первым, а номер телеграфа Чапаева — последним. Все номера телеграфов попарно различны.
Решение задачи с портала Timus Online Judge на языке C++.
Предоставляется текстовый файл с полностью проверенным и рабочем кодом.
Некоторые места могут поясняться комментариями.
Результат
Если передать Чапаеву сообщение нельзя, выведите в единственной строке «-1». В противном случае в первой строке выведите минимальное время, за которое можно доставить сообщение. Во второй строке выведите количество бойцов, которые поучаствуют в его доставке, а в третьей строке выведите через пробел их номера в порядке от Анки к Чапаеву. Бойцы 25-й дивизии занумерованы числами от 1 до n в том порядке, в котором описаны номера их мобильных телеграфов на входе. Если существует несколько способов передать сообщение за минимальное время, выведите любой из них.
Форма заказа новой работы
Не подошла эта работа?
Закажи новую работу, сделанную по твоим требованиям
