Question

Козак Вус збирається у мандрівку. У Потоколяндії n міст розташованих на прямій та пронумерованих цілими числами від 1 до n. Кожне місто характеризується певним значенням xi — координатою міста. Відстань між містами з номерами i та j рівна ∣x i−xj∣. Козак Вус хоче дізнатись мінімальну відстань, яку йому доведеться пройти, мандруючи Потоколяндією, за умови, що він повинен побувати у кожному місті хоча б один раз та завершити мандрівку у місті, з якого її почав. Ваше завдання знайти мінімальну довжину маршруту при умові, що місто, з якого почне мандрівку Козак, та його маршрут залишаються на Ваш розсуд.

Answer 1

Ответ:

#include<iostream>

#include<vector>

using namespace std;

int main() {

int num, min=1000, max=0;

cin >> num;

vector<int> arr(num);

for (int i = 0; i < num; i++) {

 cin >> arr[i];

 if (arr[i] < min) min = arr[i];

 if (arr[i] > max) max = arr[i];

  }

cout << (max - min) * 2;

}

Объяснение:

Answer 2

Це завдання можна вирішити за допомогою динамічного програмування. Основна ідея полягає в тому, щоб розглядати всі можливі міста, з яких Козак Вус може почати свою подорож, та визначити мінімальну відстань для кожного з них. Для кожного міста будемо зберігати мінімальну відстань, яку Козак Вус повинен пройти, відвідавши всі міста.

Давайте позначимо n як кількість міст у Потоколяндії і впорядкуємо міста за їх координатами в порядку зростання, тобто x1 < x2 < ... < xn.

Створимо двовимірний масив dp, де dp[i][j] буде представляти мінімальну відстань, яку Козак Вус повинен пройти, якщо він розпочинає свою подорож в місті з номером i і закінчує її в місті з номером j. Початкові значення dp можна ініціалізувати нулями.

Алгоритм для обчислення dp виглядає наступним чином:

1. Ініціалізуємо dp[i][i] = 0 для всіх i від 1 до n.

2. Для кожного підмасиву міст від довжини 2 до n (включно):

   • Перебираємо всі пари міст (i, j), які входять до цього підмасиву.
   • Для кожного проміжного міста k від i до j-1 (включно):
     • Обчислюємо dp[i][j] як мінімальну відстань між містами i та j через проміжне місто k, додавши відстань від i до k та відстань від k до j: dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + |xi - xj|).

3. Кінцева відповідь буде мінімальною відстанню з будь-якого міста i до міста 1, тобто dp[i][1] + |xi - x1|, де i варіюється від 2 до n.

Мінімальна відстань буде мінімумом з усіх таких значень.

Ось код на Python, який реалізує цей алгоритм:

pythonCopy code
def min_travel_distance(x):
    n = len(x)
    x = [0] + x  # Додамо нульовий елемент, щоб індексація співпадала з номерами міст.

    # Ініціалізація dp.
    dp = [[float('inf')] * (n + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        dp[i][i] = 0

    # Обчислення dp.
    for length in range(2, n + 1):
        for i in range(1, n - length + 2):
            j = i + length - 1
            for k in range(i, j):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + abs(x[i] - x[j]))

    # Знаходження мінімальної відстані до міста 1 з будь-якого міста i.
    min_distance = min(dp[i][1] + abs(x[i] - x[1]) for i in range(2, n + 1))

    return min_distance

# Приклад використання:
x = [0, 1, 3, 6, 9]
result = min_travel_distance(x)
print("Мінімальна відстань:", result)

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