В стране Аэродромии 30 городов, некоторые города соединены двусторонними авиарейсами. При этом, между любыми двумя городами существует только один разумный авиамаршрут (т. е. маршрут, на котором не надо пользоваться одним и тем же авиарейсом в разных направлениях).
Для каждого из городов вычислили авиарасстояние до столицы. Оно рассчитывается как минимальное количество рейсов, необходимое, чтобы долететь из этого города до столицы.
Для каждых двух городов А и В, соединённых авиарейсом, стоимость билета из города А в город В (также как и обратного) в фартингах равна наибольшему из авиарасстояний от А и В до столицы. В частности, билет до столицы из любого соединённого с ней прямым рейсом города стоит 1 фартинг; все остальные рейсы, вылетающие из этих городов, стоят 2 фартинга и так далее.
Коля много путешествовал по Аэродромии (не только на самолётах) и в конце года оказалось, что он ровно по разу воспользовался каждым из авиарейсов (то есть, для каждых двух городов А и В, соединённых прямым авиарейсом, он слетал либо из А в В, либо из В в А, причём только в одну их сторон). Какое наибольшее количество фартингов он мог потратить на авиаперелёты?
Для каждого из городов вычислили авиарасстояние до столицы. Оно рассчитывается как минимальное количество рейсов, необходимое, чтобы долететь из этого города до столицы.
Для каждых двух городов А и В, соединённых авиарейсом, стоимость билета из города А в город В (также как и обратного) в фартингах равна наибольшему из авиарасстояний от А и В до столицы. В частности, билет до столицы из любого соединённого с ней прямым рейсом города стоит 1 фартинг; все остальные рейсы, вылетающие из этих городов, стоят 2 фартинга и так далее.
Коля много путешествовал по Аэродромии (не только на самолётах) и в конце года оказалось, что он ровно по разу воспользовался каждым из авиарейсов (то есть, для каждых двух городов А и В, соединённых прямым авиарейсом, он слетал либо из А в В, либо из В в А, причём только в одну их сторон). Какое наибольшее количество фартингов он мог потратить на авиаперелёты?
More Questions From This User See All
Answers & Comments
Verified answer
Докажем по индукции, что если городов n, то авиарейсов n - 1.База индукции: если n = 1, то авиарейсов нет. Если n = 2, то есть только один авиарейс из первого города во второй.
Переход: предположим, это верно для всех количеств городов, меньших n. Отменим один авиарейс. Так как из каждого города в каждый был только один разумный авиамаршрут, то все города разобьются на две группы из l и k городов, в каждой группе из каждого города в каждый есть ровно один маршрут, в город из другой группы попасть нельзя. По предположению в первой группе l - 1 рейс, во второй k - 1 рейс, тогда с учётом отменённого рейса получаем (l - 1) + (k - 1) + 1 = (l + k) - 1 = n - 1 рейсов.
Занумеруем города.
Упорядочим все рейсы по стоимости: a1 <= a2 <= a3 <= ... <= a29.
Соседние a отличаются в стоимости не больше, чем на 1, тогда максимальная сумма будет в случае 1 <= 2 <= 3 <= ... <= 29, это соответствует ситуации, когда рейсы есть только между городами с номерами, отличающимися на 1, тогда города расположены "в линию".
Ответ: 1 + 2 + 3 + ... + 29 = 29 * 30 / 2 = 290 фартингов.