Ять островов – A, B, C, D и E соединены мостами. За проход по мосту в любую сторону взимается плата в соответствии со следующими тарифами:
Мост Тариф за проход в одну сторону, монет
A-B 1
A-C 2
B-D X
B-E 2
C-D 3
C-E 4
Необходимо начав путь с острова A посетить каждый остров не менее одного раза и после этого оказаться опять на острове A. При каком максимальном тарифе за проход по мосту B-D возможно совершить такое путешествие, затратив 14 монет? В ответе укажите целое число.
Ять островов – A, B, C, D и E соединены мостами. За проход по мосту в любую сторону взимается плата в соответствии со следующими тарифами:
Мост Тариф за проход в одну сторону, монет
A-B 1
A-C 2
B-D X
B-E 2
C-D 3
C-E 4
Необходимо начав путь с острова A посетить каждый остров не менее одного раза и после этого оказаться опять на острове A. При каком максимальном тарифе за проход по мосту B-D возможно совершить такое путешествие, затратив 14 монет? В ответе укажите целое число.
Мост Тариф за проход в одну сторону, монет
A-B 1
A-C 2
B-D X
B-E 2
C-D 3
C-E 4
Необходимо начав путь с острова A посетить каждый остров не менее одного раза и после этого оказаться опять на острове A. При каком максимальном тарифе за проход по мосту B-D возможно совершить такое путешествие, затратив 14 монет? В ответе укажите целое число.
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Мы можем представить данную задачу в виде графа, где острова - вершины, а мосты - ребра.
A/ \
1 2
/ \
B-------C
\ /
X 3
\ /
D
Мы можем заметить, что для прохождения по всем мостам необходимо пройти по мосту B-D, так как иначе мы не сможем вернуться на остров A. Таким образом, тариф за проход по мосту B-D должен быть не меньше 1 монеты.
По условию задачи, суммарный тариф за прохождение всех мостов должен быть 14 монет. Так как проход по мостам A-B и A-C должен быть выполнен, то общий тариф без учёта моста B-D уже составляет 3 монеты (1 монета за A-B и 2 монеты за A-C).
Таким образом, максимальный тариф за проход по мосту B-D, чтобы суммарный тариф за все мосты был 14 монет, равен 14 - 3 = 11 монет.
Итак, максимальный тариф за проход по мосту B-D, чтобы совершить путешествие согласно условию, и затратив 14 монет, равен 11 монетам.