Напишите код на питоне 3.12.3 Ограничение времени1 секунда Ограничение памяти64Mb Вводстандартный ввод или input.txtВыводстандартный вывод или output.txt Рассмотрим классическую…
Напишите код на питоне 3.12.3 Ограничение времени1 секунда Ограничение памяти64Mb Вводстандартный ввод или input.txtВыводстандартный вывод или output.txt Рассмотрим классическую задачу прохождения группы с одним фонариком по туннелю. Есть четыре человека и у них есть один фонарик. Нужно перевести всю группу на другой конец туннеля. По туннелю можно проходить только с фонариком и только либо вдвоем, либо в одиночку. По этой причине придется сделать пять рейсов по туннелю: три рейса туда и два рейса обратно. Туда идут двое, обратно — один, возвращая фонарик еще не прошедшей части группы. У каждого из четырех человек своя скорость передвижения по туннелю, но некоторые скорости могут совпадать. Двое идут со скоростью самого медленного в этой паре. Нужно найти минимальное время, за которое можно перевести группу по туннелю. Здесь, в зависимости от скоростей персонажей, есть две стратегии. Проиллюстрируем их на примерах. Пусть есть люди A, B, C, D. У A — время прохождения туннеля 1 минута, у B — 4 минуты, у C — 5 минут, у D — 10 минут. Здесь работает наиболее очевидная стратегия: самый быстрый переводит текущего и возвращаются с фонариком обратно за следующим. При этой стратегии нужно проходить так: A, B туда, затрачено 4 минуты; A обратно, затрачена 1 минута; A, C туда, затрачено 5 минут; A обратно, затрачена 1 минута; A, D туда, затрачено 10 минут. Общее время 4 + 1 + 5 + 1 + 10 = 21 минута. Но не всегда эта стратегия оптимальна. Уменьшим время прохождения туннеля персонажем B до 2 минут. По вышеопределенной стратегии будет 19 минут (2 + 1 + 5 + 1 + 10 = 19), но имеется более быстрое решение: A, B туда, затрачено 2 минуты; A обратно, затрачена 1 минута; C, D туда, затрачено 10 минут; B обратно, затрачено 2 минуты; A, B туда, затрачено 2 минуты. Общее время 2 + 1 + 10 + 2 + 2 = 17 минут. Заметим, что для предыдущего примера такая стратегия не работает: 4 + 1 + 10 + 4 + 4 = 23 минуты. Если же персонаж B проходит туннель за 3 минуты (а все остальные так же как и в примерах), то независимо от стратегии будет затрачено 20 минут. В этом случае считаем, что работает первая стратегия. Немного подумав, вы поймете от какого условия зависит выбор стратегии. Далее будем всегда считать, что A движется не медленнее B, B движется не медленнее C, C движется не медленнее D. Вам даны время прохождения туннеля персонажами A, C, D. Нужно найти границу border для B, такую, что если определить для B время прохождения строго меньшее чем border, то выгодна вторая стратегия, иначе первая. Формат ввода В одной строке задано три целых чисел через пробел — время прохождения туннеля персонажами A, C, D. Времена даны по неубыванию. Все числа на входе в пределах от 1 до 100. Формат вывода Вывести одно число — границу border для B, такую, что если определить время прохождения им туннеля строго меньше чем border, нужно использовать вторую стратегию, иначе — первую. Ответ может быть нецелым, поэтому вывести его нужно с одним знаком после десятичной точки.
Для решения данной задачи, нужно определить границу для времени B, чтобы правильно выбрать между двумя стратегиями.
Обозначим скорости четырех персонажей:
- A (t1) — время прохождения туннеля для первого человека.
- B (t2) — время прохождения туннеля для второго человека (которое мы ищем).
- C (t3) — время прохождения туннеля для третьего человека.
- D (t4) — время прохождения туннеля для четвертого человека.
Согласно задаче, время A, C и D даны, и мы должны выяснить, какое время t2 (для B) является критическим. Если t2 меньше этой границы, то выгоднее использовать вторую стратегию.
Определение границы
Для выбранной стратегии есть два возможных варианта:
- Первая стратегия (1) — максимальная скорость у самой медленной пары.
- Вторая стратегия (2) — необходимо учитывать, когда B быстрее или равен некоторым критическим значениям.
Теперь давайте определим границу border для B:
Первая стратегия:
- Время прохождения группой будет равно: \( t1 + t1 + t3 + t1 + t4 \)
Вторая стратегия:
- Время будет равно: \( t1 + t1 + t4 + t2 + t2 \)
Цель состоит в том, чтобы найти border, такое что, когда время B меньше этого значения, вторая стратегия будет предпочтительнее.
Для 1) и 2) у нас есть следующий результат:
- Если \( t2 < \frac{(t4 - t1) + (t3 - t1)}{2} + t1 \), то вторая стратегия выгоднее.
Это дает динамическое соотношение между обозначениями.
Реализация на Python
Вот код, который реализует данную логику:
# Считываем входные данные
t1, t3, t4 = map(int, input().split())
# Находим границу b
border = (t4 - t1 + t3 - t1) / 2 + t1
# Выводим результат
print(f"{border:.1f}")
Объяснение кода
- Мы считываем значения времени для персонажей A, C и D.
- Рассчитываем границу, используя формулу, чтобы выяснить, когда вторая стратегия предпочтительнее.
- Выводим границу с одним знаком после десятичной точки.
Запустив этот код, вы получите границу времени B, которая поможет определить, какую стратегию использовать для минимизации времени прохождения группы.
