ГДЗ по информатике 8 класс Босова, номер §3.1 № 25

§. №

Переход через мост

Группа из четырёх туристов должна пройти по мосту в темноте. Идти по мосту одновременно могут не более двух туристов. При этом они могут пользоваться только одним фонарём. Перебросить фонарь с одного берега на другой нельзя, поэтому кто-то из них должен вернуться с фонарём. Аня проходит через мост за 1 минуту, Борис — за 2 минуты, Тимур — за 5 минут и Дана — за 10 минут. Какое наименьшее время требуется туристам, чтобы все они перешли по мосту на другой берег?

Решение

Если идут двое, переход продолжается столько, сколько нужно более медленному из них. Фонарь после перехода оказывается на другом берегу, поэтому, пока на исходном берегу остаются туристы, его нужно возвращать.

Аня и Борис переходят вместе за минуты. На другом берегу оба и фонарь; прошло минуты.
Аня возвращает фонарь за минуту. На исходном берегу Аня, Тимур и Дана; прошло минуты.
Тимур и Дана переходят вместе за минут. Оба самых медленных теперь на другом берегу; прошло минут.
Борис возвращает фонарь за минуты. На исходном берегу Аня и Борис; прошло минут.
Аня и Борис переходят вместе за минуты. Все четверо на другом берегу; прошло минут.

Обоснуем минимальность. Если Тимур и Дана идут вместе, их переход занимает не меньше минут. Чтобы оба быстрых туриста в итоге также оказались на другом берегу, нужны как минимум два перехода пары Аня — Борис по минуты и два возврата фонаря. Один возврат выполняет Аня за минуту, другой — Борис за минуты: иначе после перехода медленной пары на исходном берегу не окажется фонаря для оставшегося быстрого туриста. Получаем нижнюю границу минут, которую достигает наш план.

Если Тимур и Дана идут по отдельности, их переходы занимают не менее минут. Помимо них должны состояться ещё хотя бы один переход для быстрых туристов (не менее минут) и два возврата фонаря (не менее минут). Итого не меньше минут. Значит, показанный порядок действительно даёт наименьшее время.

Ответ

минут.

Помогло?

Номер §3.1 № 25