Аналіз задачі на прикладі того, як Степан ходив в два магазини

Розбираємо задачу.

Степан і похід в магазин

https://www.e-olymp.com/uk/problems/7670

 

Сьогодні Степан чекає в гості свого друга Василя. Щоб підготуватися до зустрічі, Степану необхідно відвідати два магазини, розташованих поряд з його будинком.

 

 

Від будинку до першого магазину веде доріжка довжини d1 метрів, а до другого магазину веде доріжка довжини d2 метри. Також існує доріжка, яка безпосередньо сполучає два магазини один з одним, довжиною d3 метри.

Допоможіть Степану обчислити мінімальну відстань, яку йому буде потрібно пройти, щоб відвідати обидва магазини і повернутися додому.

Степан завжди стартує зі свого будинку. Він повинен відвідати обидва магазини, переміщаючись тільки за наявними трьома доріжками, і повернутися назад додому. При цьому його абсолютно не бентежить, якщо йому доведеться відвідати один і той же магазин або пройти по одній і тій же доріжці більше одного разу. Єдине його завдання - мінімізувати сумарну пройдену відстань.

Вхідні дані

У першому рядку вхідних даних знаходяться 3 цілих числа d1d2d3(1 ≤ d1, d2, d3 ≤ 108) - довжини доріжок.

d1 - довжина доріжки, що з'єднує будинок Степана і перший магазин;

d2 - довжина доріжки, що з'єднує будинок Степана і другий магазин;

d3 - довжина доріжки, що з'єднує два магазина.

Вихідні дані

Виведіть мінімальну кількість метрів, яку доведеться пройти Степану, щоб відвідати обидва магазини і повернутися додому.

Ліміт часу 0.1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
10 20 30
Вихідні дані #1
60
Джерело ACM-ICPC Ukraine 2016, Перший етап Україна, 16 квітня 2016 року
 
 

 
Прекрасна задача на логіку. Давайте спочатку розберем, як взагалі може ходити Степан. Розпишемо всі його можливі маршрути:
 
Отже - перший машрут. Це коли Степан йде по колу.  Тоді відстань буде d1+d3+d2.
Якщо він іде по колу, але в зворотньому напрямку,  то його шлях буде d2+d3+d1. 
Так як при обох цих вариантах відстань буде однаковою, то будемо вважати ці маршрути як один.
 
Записуємо, перший маршрут ми визначили. 
m1 = d1+d3+d2
 
Давайте подумаємо, як ще може ходити  Степан.
 
Ще один варіант: він може піти в перший магазин, потім повернутися додому, потім піти в другий магазин і знову повернутися додому. 
 
Записуємо цей маршрут:
m2 = d1+d1+d2+d2
Можна математично гарно це записати:
m2 = (d1+d2)*2
 
Наступний варіант:
Степан іде в перший магазин, потім в другий магазин. І повертається назад тією ж дорогою. 
Записуємо цей маршрут:
m3 = d1+d3+d3+d1
Можна математично гарно це записати:
m3 = (d1+d3)*2
 
 
І останній варіант:
Степан іде в другий магазин, потім в перший магазин. І повертається назад тією ж дорогою. 
Записуємо цей маршрут:
m4 = d2+d3+d3+d2
Можна математично гарно це записати:
m4 = (d2+d3)*2
 
 
В результаті аналізу ми сформували чотири маршрути.
Нам треба визначити найменший. 
Відповідна функція python вміє шукати найменше серед і елементів списку і просто змінних:
 
result = min(m1,m2,m3,m4)
 
 
Що нам допомогло розв'язати задачу? Звичайний аналіз і малюнок.
 
Успіхів!
 
 
 
 

Вхід для зареєстрованих відвідувачів