Хелп с инфой

Question

Хелп с инфой

bruhbruh bhuh Знаток (301), на голосовании 2 недели назад

На далекой планете нашей Вселенной суперземляне придумали устойчивую систему из порталов трех разных цветов: красного, синего и зеленого. Всего на этой планете 14 военных баз, и все эти базы связаны между собой порталами таким образом, что если одновременно из строя выйдут все порталы определенного цвета, то из любой базы можно будет добраться до любой другой через порталы двух оставшихся цветов, возможно, посещая промежуточные базы. При этом для того, чтобы связать две определённых базы, нужно построить отдельную пару порталов (например, через некоторый зелёный портал можно попасть только на одну конкретную базу, куда он ведёт, но не на любую другую базу с зелёным порталом). Создание пары порталов между двумя базами стоит 1000 кристаллов. Руководству Суперземли интересно, какое минимальное количество кристаллов следует затратить, чтобы создать такую систему порталов?

Answer 1

Минимальное количество кристаллов, которое нужно затратить, чтобы создать такую систему порталов, составляет 144 000 кристаллов

Answer 2

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

Пусть обозначим базы как вершины графа, а порталы между базами как рёбра. Мы должны создать граф с 14 вершинами (базами), и граф должен оставаться связным, даже если мы уберем рёбра одного цвета.

Требуется, чтобы оставшиеся два цвета могли сохранить связь между всеми базами. Это можно сделать, используя концепцию связного графа, который не должен зависеть от порта одного из цветов. Такой граф также называют 2-цвёдным графом или графом с 2-связной компонентой.

Сначала давайте проанализируем, сколько рёбер (порталов) нам нужно. В графе, чтобы он был связан, необходимо минимальное количество рёбер, равное ( n - 1 ), где ( n ) — количество вершин (в данном случае, 14). Это означает, что для полной связи нам нужно как минимум 13 рёбер. Однако это всего лишь для одного цвета.

Для того, чтобы оставшиеся два цвета оставались связными после удаления ребер одного цвета, нам нужно организовать более сложное соединение.

Мы можем воспользоваться подходом "двухсвязного" графа, который требует не менее ( 2(n - 1) ) рёбер для обеспечения связи для всех трех цветов. Это значит, что в нашем случае:

Минимальное количество рёбер для одного цвета (чтобы граф был связан): ( 14 - 1 = 13 ).
Поскольку нам нужно, чтобы оставшиеся два цвета также обеспечивали связь, нам необходимо увеличить общее количество рёбер.

Согласно теории, для полноценного графа со свойствами двусвязывания нужно не менее:

( \text{Общее количество рёбер} = 2(n - 1) = 2 \times 13 = 26 ).

Эти 26 рёбер можно разделить между всеми тремя цветами, например, по 8, 9 и 9 рёбер для каждого из цветов. В общем случае, это значит 26 порталов на трех разных цветах, что ведет нас к следующему расчету стоимости.

Исходя из того, что создание пары порталов между двумя базами стоит 1000 кристаллов, стоимость на 26 рёбер составит:

( 1000 \times 26 = 26000 ) кристаллов.

Итак, минимальное количество кристаллов, которое нужно затратить для создания системы порталов, составляет 26000 кристаллов.