e-olymp 798. Платформы

12/12/2019 by Анна Цивинская

Условие

В старых играх можно столкнуться с такой ситуацией. Герой прыгает по платформам, висящим в воздухе. Он должен перебраться от одного края экрана до другого. При прыжке с платформы на соседнюю у героя уходит $|y_{2} — y_{1}|$ энергии, где $y_{1}$ и $y_{2}$ — высоты, на которых расположены эти платформы. Кроме того, есть суперприём, позволяющий перескочить через платформу, но на это затрачивается $3\cdot\left|y_{2} — y_{1}\right|$ энергии.

Известны высоты платформ в порядке от левого края до правого. Найдите минимальное количество энергии, достаточное, чтобы добраться с $1$-ой платформы до $n$-ой (последней) и список (последовательность) платформ, по которым нужно пройти.

Входные данные

Первая строка содержит количество платформ $n (2 \leqslant n \leqslant 100000)$, вторая $n$ целых чисел, значения которых не превышают по модулю $400$ — высоты платформ.

Выходные данные

В первой строке выведите минимальное количество энергии. Во второй — количество платформ, по которым нужно пройти, а в третьей выведите список этих платформ.

Тесты

№	Ввод	Вывод
1	4 1 2 3 30	29 4 1 2 3 4
2	2 7 23	16 2 1 2
3	5 0 1 0 1 0	0 3 1 3 5

Код

#include <iostream>
#include <cmath>
using namespace std;

#define MAX 100001

int main() {
    int amount_of_pltf;
    int heights[MAX], energy[MAX], platforms[MAX], list_of_pltf[MAX];
    cin >> amount_of_pltf;
    for (int i = 1; i <= amount_of_pltf; i++) cin >> heights[i];
    
    energy[1] = 0;
    energy[2] = abs(heights[2] - heights[1]);
    platforms[1] = -1;
    platforms[2] = 1;
    
    //В цикле вычисляем значения ячеек energy[j] и platforms[j](3 ≤ j ≤ amount_of_pltf)
    for (int j = 3; j <= amount_of_pltf; j++){
        if((energy[j-1] + abs(heights[j] - heights[j-1])) < (energy[j-2] + 3 * abs(heights[j] - heights[j-2]))){
            energy[j] = energy[j-1] + abs(heights[j] - heights[j-1]);
            platforms[j] = j - 1;
        } else {
            energy[j] = energy[j-2] + 3 * abs(heights[j] - heights[j-2]);
            platforms[j] = j - 2;
        }
    }
    
    //В переменной final_amount вычисляем конечное количество платформ, по которым нужно пройти.
    int final_amount = 0;
    for (int l = amount_of_pltf; l > 0; l = platforms[l]) list_of_pltf[final_amount++] = l;
    
    cout << energy[amount_of_pltf] << "\n" << final_amount << "\n";
    for(int k = final_amount - 1; k >= 0; k--) cout << list_of_pltf[k] << " ";
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

#define MAX 100001

int main() {

int amount_of_pltf;

int heights[MAX], energy[MAX], platforms[MAX], list_of_pltf[MAX];

cin >> amount_of_pltf;

for (int i = 1; i <= amount_of_pltf; i++) cin >> heights[i];

energy[1] = 0;

energy[2] = abs(heights[2] - heights[1]);

platforms[1] = -1;

platforms[2] = 1;

//В цикле вычисляем значения ячеек energy[j] и platforms[j](3 ≤ j ≤ amount_of_pltf)

for (int j = 3; j <= amount_of_pltf; j++){

if((energy[j-1] + abs(heights[j] - heights[j-1])) < (energy[j-2] + 3 * abs(heights[j] - heights[j-2]))){

energy[j] = energy[j-1] + abs(heights[j] - heights[j-1]);

platforms[j] = j - 1;

} else {

energy[j] = energy[j-2] + 3 * abs(heights[j] - heights[j-2]);

platforms[j] = j - 2;

}

//В переменной final_amount вычисляем конечное количество платформ, по которым нужно пройти.

int final_amount = 0;

for (int l = amount_of_pltf; l > 0; l = platforms[l]) list_of_pltf[final_amount++] = l;

cout << energy[amount_of_pltf] << "\n" << final_amount << "\n";

for(int k = final_amount - 1; k >= 0; k--) cout << list_of_pltf[k] << " ";

return 0;

}

Решение

Для решения данной задачи используем несколько массивов для хранения значений затраченной энергии и подсчета платформ. Начнём с энергии. По условию у нас есть два приема для прыжка с одной платформы на другую:

Прыжок с платформы на соседнюю. Затрачивается $|y_{2} — y_{1}|$ энергии. В дальнейшем для упрощения этот вид прыжка будет называться «обычным».
Суперприём — прыжок, позволяющий перескочить через платформу. В этом случае затрачивается $3·|y_{2} — y_{1}|$ энергии. Далее по тексту этот прием будет называться «суперпрыжок».

Нам необходимо проверить какой прием эффективнее. Для этого мы сравниваем сумму затраченной энергии при «обычных» прыжках с первой платформы до третей, с энергией, затраченной при «суперпрыжке» с первой сразу на третью. Этот алгоритм мы рассматриваем для каждой платформы, начиная с $3$ и до последней. Последнее значение, которое мы получим в ходе применения наиболее выгодного приема, и будет являться минимальным количеством энергии.

Параллельно подсчету энергии необходимо нумеровать платформы, на которые мы прыгнули. Опять же, если «суперпрыжок» с первой на третью оказался выгоднее, чем «обычные» прыжки с первой до третей, то третья платформа окажется второй по счету, на которую мы прыгнули. Продолжая эти рассуждения мы подсчитываем нужные нам платформы.

Чтобы вывести список платформ, по которым мы прошли, мы записываем в новый массив номера платформ начиная с последнего значения массива platforms[amount_of_pltf]. Там же, с помощью счетчика считаем общее количество платформ.

Ссылки

Related Images:

e-olymp 806. Платформы — 3

08/12/2019 by Мария Жаркая

Задача

В старых играх можно столкнуться с такой ситуацией. Герой прыгает по платформам, висящим в воздухе. Он должен перебраться от одного края экрана до другого. При прыжке с платформы на соседнюю, у героя уходит $|y_{2} — y_{1}|^2$ энергии, где $y_{1}$ и $y_{2}$ — высоты, на которых расположены эти платформы. Кроме того, есть суперприём, позволяющий перескочить через платформу, но на это затрачивается $3|y_{3} -y_{1}|^2$ энергии.

Известны высоты платформ в порядке от левого края до правого. Найдите минимальное количество энергии, достаточное, чтобы добраться с $1$-й платформы до $n$-й (последней).

Входные данные

Первая строка содержит количество платформ $n$ $(2 \leqslant n \leqslant 10^5)$, вторая — $n$ целых чисел, значения которых не превышают по модулю $4000$ — высоты платформ.

Выходные данные

Выведите единственное целое число — искомую величину энергии.

Тесты

№	Входные данные	Выходные данные
1	4 1 2 3 30	731
2	4 0 1 6 8	40
3	8 1 15 16 23 42 10 84 5	828
4	7 57 54 -55 -34 21 88 -100	55189
5	7 -4000 4000 -4000 4000 -4000 4000 -4000	0

Код программы

#include <iostream>
using namespace std;

int main() {
    int n; long long j, sj, bj; // "цены" прыжка, суперприёма и 3-го типа прыжка
    cin >> n;
    int platforms[n]; long long energy[n]; // создаём массивы для платформ и энергии
    for (int i = 0; i < n; ++i) { 
                cin >> platforms[i]; //считываем высоты платформ  
    }
    energy[0] = 0; 
    for (int i = 1; i < n; ++i) {
        // обычный прыжок
        j = (platforms[i] - platforms[i - 1]) * (platforms[i] - platforms[i - 1]);
        // 3-й тип прыжка
        bj = (platforms[i] - platforms[i + 1]) * (platforms[i] - platforms[i + 1]) + 
        3 * (platforms[i + 1] - platforms[i - 1])*(platforms[i + 1] - platforms[i - 1]);
        // суперприём 
        if (i == 1) sj = max(j, bj);
        else sj = 3 * (platforms[i] - platforms[i - 2]) * (platforms[i] - platforms[i - 2]);
        if (i == n - 1) bj = max(j, sj);
        //количество энергии на i-й платформе
        energy[i] = min(energy[i - 1] + bj, min(energy[i - 1] + j, energy[i - 2] + sj));
    }
    cout << energy[n - 1];
}

#include <iostream>

using namespace std;

int main() {

int n; long long j, sj, bj; // "цены" прыжка, суперприёма и 3-го типа прыжка

cin >> n;

int platforms[n]; long long energy[n]; // создаём массивы для платформ и энергии

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

cin >> platforms[i]; //считываем высоты платформ

}

energy[0] = 0;

for (int i = 1; i < n; ++i) {

// обычный прыжок

j = (platforms[i] - platforms[i - 1]) * (platforms[i] - platforms[i - 1]);

// 3-й тип прыжка

bj = (platforms[i] - platforms[i + 1]) * (platforms[i] - platforms[i + 1]) +

3 * (platforms[i + 1] - platforms[i - 1])*(platforms[i + 1] - platforms[i - 1]);

// суперприём

if (i == 1) sj = max(j, bj);

else sj = 3 * (platforms[i] - platforms[i - 2]) * (platforms[i] - platforms[i - 2]);

if (i == n - 1) bj = max(j, sj);

//количество энергии на i-й платформе

energy[i] = min(energy[i - 1] + bj, min(energy[i - 1] + j, energy[i - 2] + sj));

}

cout << energy[n - 1];

}

Решение

Чтобы решить задачу, мы создадим массив $energy$, где будем хранить минимальную энергию, которую герой потратит для прыжка на очередную $i$-ю платформу. Для этого необходимо для каждой платформы, начиная со второй, рассмотреть три вида прыжка:

прыжок с предыдущей $i — 1$ платформы.
суперприём, то есть прыжок c $i — 2$ платформы.
3-й вид: суперприём с $i — 1$ платформы на $i + 1$ и прыжок назад на $i$.

«Цены» за обычный прыжок и суперприём мы можем найти из формул данных в условии, с 3-м же сложнее — результатом будет сумма «цены» суперприёма $3(y_{i+1} — y_{i-1})^2$ и «цены» прыжка назад $(y_{i} — y_{i+1})^2$.

Для понимания схемы можно рассмотреть в качестве примера второй тест.
Синим обозначен 3-ий тип. Красными цифрами — весь путь.

второй тест

Каждый из 3-х путей даст своё значение энергии, равное сумме «цены» прыжка на $i$-ю платформу и значения в той, из которой герой совершил прыжок. Наименьшей энергией для этой платформы будет минимум из этих трех значений.
На второй платформе $(i = 1)$ в случае суперприёма мы выходим за границы массива и получаем независимое значение, поэтому эффективнее будет в качестве «цены» выбирать максимум из двух других уже найденных значений. Аналогично на последней $(i = n — 1)$ и 3-м типе прыжка, максимум будет невыгодным и соответственно не будет выбран как минимум в $energy_{i}$.

Ссылки

Условие задачи на e-olymp
Код программы на ideone

Related Images:

e-olymp-8577. Супер платформи

25/06/2019 by Евгений Рудницкий

Условие

У багатьох старих іграх з двовимірною графікою можна зіткнутися з такою ситуацією. Який-небудь герой стрибає по платформам (або острівкам), які висять у повітрі. Він повинен перебратись від одного краю екрану до іншого. При цьому, при стрибку з однієї платформи на сусідню, у героя витрачається $\left|y_2–y_1\right|$енергії, де $y_2$ та $y_1$ – висоти, на яких розміщені ці платформи. Крім того у героя є суперприйом, який дозволяє перестрибнути через платформу, причому на це витрачається $3·|y_2–y_1|$ одиниць енергії. Кількість використань суперприйому обмежена й повинна перебувати в межах від $k_{min}$ до $k_{max}$ разів (обидві межі включно). Звичайно ж, енергію потрібно витрачати максимально економно.

Припустимо, що вам відомі координати усіх платформ у порядку від лівого краю до правого та обмеження на кількість використань суперприйому $k_{min}$ та $k_{max}$. Чи зможете ви знайти, яку мінімальну кількість енергії потрібно герою, щоб дістатись від першої платформи до останньої?

Вхідні дані

У першому рядку записана кількість платформ $n (1 \leq n ≤ 10000)$. Другий рядок містить n натуральних чисел, які не перевищують 30000 – висоти, на яких розміщено платформи. Третій рядок містить два цілі невід’ємні числа $k_{min}$ та $k_{max}$ $\left(0 ≤ k_{min} ≤ k_{max} ≤ \frac{n–1}{2}\right)$.

Вихідні дані

Виведіть єдине число – мінімальну кількість енергії, яку повинен витратити гравець на подолання платформ (звісно ж у припущенні, що cheat-коди використовувати не можна).

Тесты

№	Ввод	Вывод
1	3 1 5 10 0 1	9
2	9 1 3 2 3 8 10 25 17 25 2 4	24

Код

#include <iostream>

using namespace std;
#define ll long long

int main() {
    ll n, i, j, minjumps, maxjumps, me = 1000000000;
    cin >> n;
    ll p[n];
    for (i = 0; i < n; i++) {
        cin >> p[i];
    }
    cin >> minjumps >> maxjumps;
    ll a[2][n + 1];
    a[0][0] = 0;
    for (i = 1; i < n; i++)a[0][i] = a[0][i - 1] + abs(p[i] - p[i - 1]);
    if (minjumps == 0)me = a[0][n - 1];
    for (j = 1; j <= maxjumps; j++) {
        a[j % 2][j * 2] = a[(j - 1) % 2][j * 2 - 2] + 3 * abs(p[j * 2] - p[j * 2 - 2]);
        for (i = j * 2 + 1; i < n; i++) {
            a[j % 2][i] = min(a[j % 2][i - 1] + abs(p[i - 1] - p[i]), a[(j - 1) % 2][i - 2] + 3 * abs(p[i - 2] - p[i]));
        }
        if ((j >= minjumps) and (me > a[j % 2][n - 1])) { me = a[j % 2][n - 1]; }
    }
    cout << me << endl;
    return 0;
}

#include <iostream>

using namespace std;

#define ll long long

int main() {

ll n, i, j, minjumps, maxjumps, me = 1000000000;

cin >> n;

ll p[n];

for (i = 0; i < n; i++) {

cin >> p[i];

}

cin >> minjumps >> maxjumps;

ll a[2][n + 1];

a[0][0] = 0;

for (i = 1; i < n; i++)a[0][i] = a[0][i - 1] + abs(p[i] - p[i - 1]);

if (minjumps == 0)me = a[0][n - 1];

for (j = 1; j <= maxjumps; j++) {

a[j % 2][j * 2] = a[(j - 1) % 2][j * 2 - 2] + 3 * abs(p[j * 2] - p[j * 2 - 2]);

for (i = j * 2 + 1; i < n; i++) {

a[j % 2][i] = min(a[j % 2][i - 1] + abs(p[i - 1] - p[i]), a[(j - 1) % 2][i - 2] + 3 * abs(p[i - 2] - p[i]));

}

if ((j >= minjumps) and (me > a[j % 2][n - 1])) { me = a[j % 2][n - 1]; }

}

cout << me << endl;

return 0;

}

Решение

В решении суперприёмы из условия для удобства буду называть суперпрыжками.
Решим эту задачу динамически. На каждом шаге будем искать масив, где записано сколько минимально надо потратить энергии что б добраться до каждой платформы, сделав ровно $j$ суперпрыжков. Легко получить рекурсивную зависимость: для того, что бы попасть на $i$ платформу нам надо либо прыгнуть с предыдущей $(a_{j (i-1)}+|p_i-p_{i-1}|)$ либо сделать суперпрыжок с платформы под номером $i-2$ $( a_{(j — 1)(i — 2)} + 3|p_{i — 2} — p_i| )$. Не забудем про то, что не всегда можно прыгнуть с предыдущей так как мы могли бы и не попасть на нее за $j$ суперпрыжков. Таким образом для некоторых платформ( а именно первых в каждом масиве) мы будем делать суперпрыжок с платформы под номером $i-2$. На каждом шаге если нам разрешено сделать столько суперпрыжком сколько мы сделали обновляем общее минимальное количество затраченной энергии если оно больше чем результат, полученный нами на последней платформе. Таким образом на каждом шаге мы будем получать минимальные затраты для определенного количества прыжков. Таким образом минимальное из этих самых ответов и будет тем что требуется в задаче.