Question

В стране Аэродромии 30 городов, некоторые города соединены двусторонними авиарейсами. При этом, между любыми двумя городами существует только один разумный авиамаршрут (т. е. маршрут, на котором не надо пользоваться одним и тем же авиарейсом в разных направлениях). Для каждого из городов вычислили авиарасстояние до столицы. Оно рассчитывается как минимальное количество рейсов, необходимое, чтобы долететь из этого города до столицы. Для каждых двух городов А и В, соединённых авиарейсом, стоимость билета из города А в город В (также как и обратного) в фартингах равна наибольшему из авиарасстояний от А и В до столицы. В частности, билет до столицы из любого соединённого с ней прямым рейсом города стоит 1 фартинг; все остальные рейсы, вылетающие из этих городов, стоят 2 фартинга и так далее. Коля много путешествовал по Аэродромии (не только на самолётах) и в конце года оказалось, что он ровно по разу воспользовался каждым из авиарейсов (то есть, для каждых двух городов А и В, соединённых прямым авиарейсом, он слетал либо из А в В, либо из В в А, причём только в одну их сторон). Какое наибольшее количество фартингов он мог потратить на авиаперелёты?

Answer 1

Докажем по индукции, что если городов 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 фартингов.

Answer 2

Finding the Maximum Amount of Fartings Spent on Air Travel

To find the maximum amount of fartings Kolya could have spent on air travel, we need to consider the given conditions and constraints. Kolya traveled to each city exactly once and used each direct flight between two cities exactly once. The cost of a ticket from city A to city B (and vice versa) is equal to the greater of the air distances from A and B to the capital. The cost of a direct flight to the capital is 1 farting, and all other flights cost 2 fartings.

Approach to Solving the Problem

To solve this problem, we can use a graph theory approach. We can represent the cities as nodes and the direct flights between them as edges. Then, we can use a traversal algorithm to find the maximum amount of fartings Kolya could have spent on air travel.

Calculation Steps

1. We need to find the maximum spanning tree of the graph representing the direct flights between the cities. This will ensure that Kolya travels to each city exactly once and uses each direct flight exactly once.

2. Once we have the maximum spanning tree, we can calculate the total cost of Kolya's air travel by summing the costs of the direct flights according to the given conditions.

Conclusion

By following this approach, we can determine the maximum amount of fartings Kolya could have spent on air travel in the given scenario.