Массив: Последнее дело Оушена. Составьте маршрут, следуя которому, Оушен успеет ограбить все банки.

@Xait · Регистрация: 04.11.2017

Оушен отправляется на пенсию! Но для обеспечения безбедной старости он решил напоследок
ограбить n банков. Так совпало, что все банки расположены на прямой. Позиция банка с номером
i характеризуется целым числом ai — координатой этого банка (в км) на прямой. Перед началом
операции Оушен может подъехать к любому банку. Казалось бы, все должно было пройти гладко.
Но выяснилось, что из банка с номером index деньги увезут в неизвестном направлении ровно через
t минут после начала операции! При этом банк можно успеть ограбить в момент времени t, но не
позже.
Если Оушен не ограбит хотя бы один банк, ему не хватит на безбедную старость. Чтобы не привлекать лишнего внимания, грабитель решил ездить со скоростью не выше 60 км/ч (1 км в минуту).
Составьте маршрут, следуя которому, он успеет ограбить все банки. Учтите, что Оушен хочет на
пенсию как можно скорее, поэтому из всех маршрутов выберите оптимальный (т. е. при передвижении по которому будет потрачено меньше всего времени). Если таких маршрутов несколько, Оушена
устроит любой. Можете считать, что благодаря отточенному мастерству Оушен грабит любой банк
моментально.

Формат входных данных
В первой строке заданы числа n и t (1 <= n, t <= 100).
Во второй строке задано n чисел ai (|ai| <= 100), расположенных в порядке возрастания.
В третьей строке задано число index (1 <= index <= n).

Формат выходных данных
В первой строке выведите число минут, которое потребуется Оушену для ограбления всех банков.
Во второй строке выведите n чисел — порядок ограбления банков.

Примеры
Ввод:
5 5
1 4 9 16 25
2
Вывод:
24
1 2 3 4 5

Ввод:
6 4
1 2 3 6 8 25
5
Вывод:
31
5 4 3 2 1 6

@nalbe666 · 01.09.2019, 13:45

C++

#include <iostream>
 
void print(int16_t i, int16_t j) {
    if (i <= j) {
        for (; i <= j; ++i) {
            std::cout << i << ' ';
        }
    }
    else {
        for (; i >= j; --i) {
            std::cout << i << ' ';
        }
    }
}
 
int main()
{
    uint16_t n, t, ind;
    int16_t arr[100];
    std::cin >> n >> t;
    for (uint16_t i = 0; i < n; ++i) {
        std::cin >> arr[i];
    }
    std::cin >> ind;
 
    uint16_t lhs = arr[ind - 1] - arr[0];
    uint16_t rhs = arr[n - 1] - arr[ind - 1];
    if (lhs <= t) {
        std::cout << arr[n - 1] - arr[0] << '\n';
        print(1, n);
    }
    else if (rhs <= t) {
        std::cout << arr[n - 1] - arr[0] << '\n';
        print(n, 1);
    }
    else {
        if (lhs <= rhs) {
            std::cout << lhs * 2 + rhs << '\n';
            print(ind, 1);
            print(ind + 1, n);
        }
        else {
            std::cout << lhs + rhs * 2 << '\n';
            print(n, n + 2 - ind);
            print(1, n + 1 - ind);
        }
    }
 
    return 0;
}

?

@Xait · 01.09.2019, 14:02 **[ТС]**

nalbe666, почти да, дал ошибку в 21 тесте

@yankis · 02.09.2019, 21:10

нашли ошибку? Тоже аналогичное решение на Питоне, не могу придумать, какой тест не проходит, что-то не проверили.

@nalbe666 · 03.09.2019, 00:47

Есть предположения касаемо повторяющихся чисел и вывода. Киньте ссылку на сам сайт с задачей.

@Xait · 03.09.2019, 05:24 **[ТС]**

yankis, пока нет

Добавлено через 21 секунду
nalbe666, Войти в контест: http://ejudge.algocode.ru/cgi-... t_id=10502

Логин: summer-qual-2019-104

Пароль: tROcxeZZ92tTgqo

Задача С

@Stas_ale · 03.09.2019, 07:27

Xait, нужна помощь? Я нашел ошибку. Но ты решаешь те же задачи, что и я. Проверь 4 условие.

@nalbe666 · 03.09.2019, 21:50

C++

#include <iostream>
 
void print(int16_t i, int16_t j) {
    if (i <= j) {
        for (; i <= j; ++i) {
            std::cout << i << ' ';
        }
    }
    else {
        for (; i >= j; --i) {
            std::cout << i << ' ';
        }
    }
}
 
int main()
{
    uint16_t n, t, ind;
    int16_t arr[100];
    std::cin >> n >> t;
    for (uint16_t i = 0; i < n; ++i) {
        std::cin >> arr[i];
    }
    std::cin >> ind;
 
    uint16_t lhs = arr[ind - 1] - arr[0];
    uint16_t rhs = arr[n - 1] - arr[ind - 1];
    if (lhs <= t) {
        std::cout << arr[n - 1] - arr[0] << '\n';
        print(1, n);
    }
    else if (rhs <= t) {
        std::cout << arr[n - 1] - arr[0] << '\n';
        print(n, 1);
    }
    else {
        if (lhs <= rhs) {
            std::cout << lhs * 2 + rhs << '\n';
            print(ind, 1);
            print(ind + 1, n);
        }
        else {
            std::cout << lhs + rhs * 2 << '\n';
            print(ind, n);
            print(ind - 1, 1);
        }
    }
    std::cout << "\n\n";
    return 0;
}

Изначально не понял, чего надо было сделать. Я их нумеровал, как на карте, а нужен был порядок индексов, с какого начать и какой следующий..

@Xait · 05.09.2019, 06:50 **[ТС]**

Stas_ale, 4 задачу?

Добавлено через 2 минуты
Ну, nalbe666, Благодарю спасибо вам большое))

@Xait 2 / 2 / 0 Регистрация: 04.11.2017 Сообщений: 58
		1
	Массив: Последнее дело Оушена. Составьте маршрут, следуя которому, Оушен успеет ограбить все банки. 29.08.2019, 22:43. Показов 1218. Ответов 8 Метки нет (Все метки) Оушен отправляется на пенсию! Но для обеспечения безбедной старости он решил напоследок ограбить n банков. Так совпало, что все банки расположены на прямой. Позиция банка с номером i характеризуется целым числом ai — координатой этого банка (в км) на прямой. Перед началом операции Оушен может подъехать к любому банку. Казалось бы, все должно было пройти гладко. Но выяснилось, что из банка с номером index деньги увезут в неизвестном направлении ровно через t минут после начала операции! При этом банк можно успеть ограбить в момент времени t, но не позже. Если Оушен не ограбит хотя бы один банк, ему не хватит на безбедную старость. Чтобы не привлекать лишнего внимания, грабитель решил ездить со скоростью не выше 60 км/ч (1 км в минуту). Составьте маршрут, следуя которому, он успеет ограбить все банки. Учтите, что Оушен хочет на пенсию как можно скорее, поэтому из всех маршрутов выберите оптимальный (т. е. при передвижении по которому будет потрачено меньше всего времени). Если таких маршрутов несколько, Оушена устроит любой. Можете считать, что благодаря отточенному мастерству Оушен грабит любой банк моментально. Формат входных данных В первой строке заданы числа n и t (1 <= n, t <= 100). Во второй строке задано n чисел ai (\|ai\| <= 100), расположенных в порядке возрастания. В третьей строке задано число index (1 <= index <= n). Формат выходных данных В первой строке выведите число минут, которое потребуется Оушену для ограбления всех банков. Во второй строке выведите n чисел — порядок ограбления банков. Примеры Ввод: 5 5 1 4 9 16 25 2 Вывод: 24 1 2 3 4 5 Ввод: 6 4 1 2 3 6 8 25 5 Вывод: 31 5 4 3 2 1 6 __________________ Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь 0

@Xait 2 / 2 / 0 Регистрация: 04.11.2017 Сообщений: 58
	01.09.2019, 14:02 [ТС]	3
	nalbe666, почти да, дал ошибку в 21 тесте Миниатюры 0

@yankis 0 / 0 / 0 Регистрация: 11.04.2018 Сообщений: 28
	02.09.2019, 21:10	4
	нашли ошибку? Тоже аналогичное решение на Питоне, не могу придумать, какой тест не проходит, что-то не проверили. 0

@nalbe666 817 / 504 / 211 Регистрация: 19.01.2019 Сообщений: 1,196
	03.09.2019, 00:47	5
	Есть предположения касаемо повторяющихся чисел и вывода. Киньте ссылку на сам сайт с задачей. 0

@Xait 2 / 2 / 0 Регистрация: 04.11.2017 Сообщений: 58
	03.09.2019, 05:24 [ТС]	6
	yankis, пока нет Добавлено через 21 секунду nalbe666, Войти в контест: http://ejudge.algocode.ru/cgi-... t_id=10502 Логин: summer-qual-2019-104 Пароль: tROcxeZZ92tTgqo Задача С 0

@Stas_ale 2 / 2 / 0 Регистрация: 24.01.2019 Сообщений: 8
	03.09.2019, 07:27	7
	Xait, нужна помощь? Я нашел ошибку. Но ты решаешь те же задачи, что и я. Проверь 4 условие. 1

@Xait 2 / 2 / 0 Регистрация: 04.11.2017 Сообщений: 58
	05.09.2019, 06:50 [ТС]	9
	Stas_ale, 4 задачу? Добавлено через 2 минуты Ну, nalbe666, Благодарю спасибо вам большое)) 0

Опции темы