Question

В Тридесятом государстве есть 2019 городов, каждые два из которых соединены прямыми авиалиниями. Сотруднику авиакомпании под Новый год дали премию: 217 бесплатных перелетов (один перелет – из города в город, только в одну сторону). Он хочет посетить как можно большее количество городов и вернуться домой, пользуясь только премиальными перелетами. Какое наибольшее количество городов ему удастся посетить? (Город, в котором он живет, в ответе не учитывается).

Answer 1

216, потому что он может за один перелет перелетать из города в город, а начальный город не учитывается.
Вот только я не понял, а для чего дана информация про количество городов?

Answer 2

Для решения этой задачи нам потребуется использовать графический алгоритм. Мы можем представить каждый город в виде вершины графа, а прямые авиалинии между городами - ребра графа.

Из условия задачи известно, что каждые два города соединены прямыми авиалиниями. Это означает, что граф является полным графом, то есть каждая вершина связана со всеми остальными вершинами. В полном графе с 2019 вершинами количество ребер можно вычислить по формуле:

n(n-1)/2,

где n - количество вершин. В нашем случае:

2019(2019-1)/2 = 2037171.

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

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

Количество возможных путей можно рассчитать по формуле:

n-1 * n-3 * n-5 * ... * 1,

где n - количество ребер в графе. В нашем случае:

2037171-1 * 2037171-3 * 2037171-5 * ... * 1 = 2037170 * 2037168 * 2037166 * ... * 1.

Теперь мы знаем, что сотрудник авиакомпании сможет посетить максимальное количество городов, равное половине от общего количества ребер в графе, то есть:

2037170 * 2037168 * 2037166 * ... * 1 / 2 = 1042237868585.

Таким образом, сотрудник авиакомпании сможет посетить 1042237868585 городов.