Входной файл: set.txt Выходной файл: стандартный выход Время на тест: 2 секунды Тесты к задаче:Скачать
В городе М компьютерная сеть строится следующим образом:
к первому компьютеру (назовем его главным) может быть подключено не более 10 компьютеров (назовем их компьютерами 1-го уровня);
к каждому компьютеру 1-го уровня может быть подключено не более 10 компьютеров (назовем их компьютерами 2-го уровня);
и т.д. (количество уровней не более 10).
Каждый компьютер в сети имеет уникальный номер, который является натуральным числом, не превышающим 32000. Стоимость 1 минуты связи между любыми 2-мя компьютерами сети i и j равна сумме стоимостей 1 минуты работы каждого компьютера на маршруте от i до j включительно. Стоимость (С i ) 1 минуты работы любого компьютера сети с номером i определяется по формуле: С i = [i /10] (т.е. целочисленное деление номера i на 10).
Необходимо определить: между какими двумя компьютерами сети стоимость 1 минуты связи максимальная.
Последовательность соединения компьютеров в сети задается строкой символов (длиною не более 100) следующим образом (см. пример в конце задачи):
первым записывается номер главного компьютера;
затем записываются через знак “ , ” номера всех компьютеров, встретившихся при последовательном обходе всех связей (ветвей) в сети;
завершается обход возвратом в начальную вершину: т.е. последним записывается номер главного компьютера.
Строка, задающая сеть, вводится из файла Set.txt.
Результат выводится на экран в следующем формате:
{1-я строка вывода: <2 целых числа через пробел в порядке возрастания> – номера компьютеров сети с максимальной стоимостью 1 минуты связи между ними (при наличии нескольких вариантов выводится один любой)}
{2-я строка вывода: <целое число> – стоимость минуты связи в сети между 2-мя компьютерами, указанными в 1-й строке вывода>}
Пример. Рассмотрим сеть на приведенном рисунке.
Строка, задающая сеть: 20,10,5,10,13,10,20,19,15,19,16,11,16,19,20,12,20
Максимальная стоимость 1 минуты связи для заданной сети будет между компьютерами 11 и 13 и ее значение равняется 7 (так как [11/10]+ [16/10]+ [19/10]+ [20/10]+ [10/10]+ [13/10]=7)
Соответственно, ввод и вывод данных для рассматриваемого примера имеет вид:
20,10,5,10,13,10,20,19,15,19,16,11,16,19,20,12,20 <1-я строка ввода>
11 13 <1-я строка вывода> 7 <2-я строка вывода>