Задача №1646. Деревья в саду
Центральный сад страны Олимпия настолько большой, что один садовник не в силах его обслуживать. Было принято решение разделить сад на две части. Определенные деревья будут отнесены к первой части, а оставшиеся – ко второй. Одна из частей сада может остаться пустой.
Между каждой парой деревьев в саду протоптаны тропинки. Когда садовники идут от дерева к дереву, они обязательно идут по тропинке соединяющей непосредственно эти два дерева. Длина тропинки одинакова при перемещении в обе стороны.
Для упрощения работы садовников, разделение решили проводить так, чтобы длина самой длинной тропинки между парой деревьев, принадлежащих одной и той же части, была минимальна.
Напишите программу, которая по информации о длинах тропинок между всеми парами деревьев находит длину самой длинной тропинки между деревьями из одной части сада, при оптимальном разделении сада на части.
Формат входных данных
Первая строка входного файла содержит целое число N (2≤N≤1000) – количество деревьев в саду. Каждая i-ая из последующих N-1-ой строк содержит N-i чисел, которые последовательно представляют длины тропинок между i-ым деревом и деревьями с i+1-го до N-го. Все числа целые, неотрицательные, и не превышают 106.
Формат выходных данных
Единственная строка выходного файла должна содержать одно целое число – минимальную для всех возможных разбиений сада длину самой длинной тропинки между деревьями в одной из частей сада.
3 10 12 13
10