07/04/2025 05:57:28

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

1378. Траляля и Труляля делят лес

Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Поссорившись, Траляля и Труляля решили поделить все деревья в лесу. Перед разделом леса они измерили расстояние между каждой парой деревьев. При этом путь между этими деревьями проходил вдали от других деревьев. Таким образом, может оказаться так, что "прямое" расстояние

$D_{ij}$ между деревьями

$i$ и

$j$ может оказаться больше суммы путей

$D_"ik"$ и

$D_"kj"$ . Такой способ измерения расстояний был использован по следующей причине: при охране своих деревьев может потребоваться быстро бежать от одного дерева к другому, а если на пути окажется какое-то дерево, то можно удариться о него лбом.

Напишите программу, которая разделит деревья в лесу между Траляля и Труляля таким образом, чтобы максимальное расстояние между своими деревьями у каждого было минимально. Максимальное расстояние между деревьями Траляля должно быть больше или равно максимальному расстоянию между деревьями Труляля.

Первая строка ввода содержит одно целое число

$N$ (

$3\ ≤\ N\ ≤\ 100$ ). Далее следует

$(N-1)$ строка,

$i$ -я cтрока ввода содержит

$(i-1)$ целое число

$D_{ij}$ в диапазоне от 1 до

$10^6$ – расстояния от

$i$ -го до

$j$ -го, где

$j$ от 1 до

$i-1$ .

Вывести в первой строке одно целое число

$K$ (

$K\ <\ N$ ) – количество деревьев у Траляля в распределении, минимизирующих максимальное расстояние между своими деревьями, во второй строке выведите

$K$ чисел – номера этих деревьев. Если существует несколько вариантов, минимизирующих расстояние между деревьями Траляля, выведите из них вариант, минимизирующий расстояние между деревьями Труляля.

Пример ввода

Пример вывода

3
1 2 4