This page is hosted for free by zzz.com.ua, if you are owner of this page, you can remove this message and gain access to many additional features by upgrading your hosting to PRO or VIP for just 32.50 UAH.
Do you want to support owner of this site? Click here and donate to his account some amount, he will be able to use it to pay for any of our services, including removing this ad.

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

Друк

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

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

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)
 
 
Що нам допомогло розв'язати задачу? Звичайний аналіз і малюнок.
 
Успіхів!