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 657. Игра с монетами

22/06/2019 by Богдан Подгорный

Задача взята с сайта e-olymp

Условие

Однокопеечные монетки разложены в стопки (в стопках может быть различное количество монет), а стопки поставлены на столе в ряд слева направо. Двое противников по очереди делают ходы. Ход состоит в том, что один из игроков берет слева несколько стопок подряд, не меньше одной, но и не больше, чем перед этим взял его соперник. Первый игрок своим первым ходом берет не более $ K$ стопок. Игра заканчивается, когда стопок не остается. Требуется найти максимальное число монет, которое может получить первый участник после окончания игры, если второй игрок тоже старается ходить так, чтобы получить как можно больше монет.

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

В первой строке находится сначала число стопок $ N,$ за ним идут $ N$ чисел, задающих количество монет в стопках слева направо, а затем число $ K.$ Все числа в строке разделены пробелами.
$ 1 \leqslant N \leqslant 180, 1 \leqslant K \leqslant 80,$ количество монет в стопке — не менее $ 1$ и не более $ 20 000$.

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

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

Тесты

№	Inputs	Outputs
1	3 4 9 1 3	14
2	4 1 2 2 7 3	5
3	5 3 4 8 1 7 2	18
4	12 67 8 6 12 6 90 54 89 145 32 45 65 4	357
5	14 32 53 5 52 9 8 17 5 87 44 51 12 15 56 10	312
6	14 76 112 3 1 98 4 172 33 65 90 2 71 18 32 14	777

Код

#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;

int sum[190][90][3];

int solution(vector<int>&arr, int l, int k, int p){
    if(sum[l][k][p]){
        return sum[l][k][p];
    }
    int ans = 0;
    if(arr.size() - l <= k){
        for(int i = l; i < arr.size(); i++){
            ans += arr[i];
        }
        if(p == 2){
            sum[l][k][p] = 0;
            return sum[l][k][p];
        }
        sum[l][k][p] = ans;
        return sum[l][k][p];
    }
    if(p == 1){
        int temp = 0;
        for(int i = 1; i <= k; i++){
            temp += arr[(l-1) + i];
            ans = max(ans, temp + solution(arr, l+i, i, 3-p));
        }
        sum[l][k][p] = ans;
        return sum[l][k][p];
    }
    else{
        int ans = INT_MAX;
        for(int i = 1; i <= k; i++){
            ans = min(ans, solution(arr, l+i, i, 3-p));
        }
        sum[l][k][p] = ans;
        return sum[l][k][p];
    }
}

int main() {
    int n, k, a;
    vector<int> coins;
    cin >> n;
    for(int i = 0; i > a;
        coins.push_back(a);
    }
    cin >> k;
    cout << solution(coins, 0, k, 1);
    return 0;
}

#include <iostream>

#include <vector>

#include <limits.h>

using namespace std;

int sum[190][90][3];

int solution(vector<int>&arr, int l, int k, int p){

if(sum[l][k][p]){

return sum[l][k][p];

}

int ans = 0;

if(arr.size() - l <= k){

for(int i = l; i < arr.size(); i++){

ans += arr[i];

}

if(p == 2){

sum[l][k][p] = 0;

return sum[l][k][p];

}

sum[l][k][p] = ans;

return sum[l][k][p];

}

if(p == 1){

int temp = 0;

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

temp += arr[(l-1) + i];

ans = max(ans, temp + solution(arr, l+i, i, 3-p));

}

sum[l][k][p] = ans;

return sum[l][k][p];

}

else{

int ans = INT_MAX;

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

ans = min(ans, solution(arr, l+i, i, 3-p));

}

sum[l][k][p] = ans;

return sum[l][k][p];

}

int main() {

int n, k, a;

vector<int> coins;

cin >> n;

for(int i = 0; i > a;

coins.push_back(a);

}

cin >> k;

cout << solution(coins, 0, k, 1);

return 0;

}

Решение

Анализируя задачу, становится понятно, что ее можно решить методами динамического программирования, а именно трехмерная динамика по параметрам: количество уже взятых стопок — l, количество стопок, которые можно взять kи какой игрок сейчас ходит p. Каждый игрок старается ходить оптимально, тогда для первого игрока задача взять максимальное количество монет, а для второго игрока задача оставить наименьшее количество монет оппоненту. Решение исполнено с помощью рекурсии, где терминальный случай-когда в массиве осталось количество стопок, меньшее или равное тому, сколько игрок может взять. Также стоит проверять высчитывалась ли раньше данная позиция, иначе задача не зайдет по времени.

Ссылки

Related Images:

e-olymp 203. Кубики-2

02/01/2018 by Данила Савчак

Задача

После Нового года Витэк решил стать банкиром и поэтому стал играться только кубиками с цифрами, ведь будущая профессия требовала умения четко и быстро оперировать с цифрами и числами. И опять ему нравились такие расположения кубиков, на которых последовательность изображенных на них цифр читалась в обеих направлениях одинаково.
Каждое утро, придя в детсад Витэк сразу смотрел на разложенные на полу кубики, и если последовательность не читалась в обеих направлениях одинаково, доставал какое-то количество новых кубиков и размещал их правее, чтобы получить такое размещение кубиков, которое соответствовало его требованию.
Какое наименьшее количество кубиков нужно доставить для этого Витэку?

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

В первой строке – количество разложенных перед Витэком кубиков [latex]N[/latex] [latex](1 ≤ N ≤ 100)[/latex], в следующей строке последовательность из [latex]N[/latex] цифр на кубиках через пробел.

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

Наименьшее количество кубиков, которое нужно правее доставить Витэку.

Тесты

#	Входные данные	Выходные данные
1	3 1 2 3	2
2	5 1 2 3 4 4	3
3	2 1 2	1
4	2 1 1	0

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

#include <iostream>
using namespace std;

int main() {
    int n, h=0, k=0;
    cin >> n;
    int A[n];
    for ( int i = 0; i < n; i++ ) {
        cin >> A[i];
    }
    for ( int i = 0; i < n; i++ ) {
        if ( A[n-1] == A[i] ) {
            int t = 1;
            for ( int j = i + 1; j < n - 1; j++ ) {
                if ( A[j] != A[ n - 1 - t ] ) {
                    k++;
                }
                t++;
            }
            if ( k == 0 ) {
                h = i;
                break;
            }
            else k = 0;
        }
    }
    cout << h;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, h=0, k=0;

cin >> n;

int A[n];

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

cin >> A[i];

}

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

if ( A[n-1] == A[i] ) {

int t = 1;

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

if ( A[j] != A[ n - 1 - t ] ) {

k++;

}

t++;

}

if ( k == 0 ) {

h = i;

break;

}

else k = 0;

}

cout << h;

return 0;

}

Решение задачи

Читаем поток данных переводя каждое прочитанное число в элемент массива. Для каждого элемента массива проверяем его равенство с последний и если да, то через два цикла(начиная с начала и с конца) проверяем равенство остальных элементов массива по двое и если да, то увеличиваем переменную, от которой будет зависеть ответ, если она в конце будет равна [latex]0[/latex], то выведем число равное номеру элемента массива равного последнему.

Ссылки

Условие задачи на e-olymp.com.

Код решения на ideone.com.

Related Images:

Heat Detector

16/10/2014 by Вустянюк Ігор Дмитрович

Задача

Речь пойдёт о первой задаче уровня Medium на сайте codingame.com. По сюжету Бэтмен должен отыскать бомбу в многоэтажном доме. Ему известно количество этажей и количество окон на каждом этаже. Ему также известно направление, в котором находится бомба. Бэтмену нужно как можно быстрее её найти. Процесс поиска выглядит следующим образом: Бэтмен заглядывает в какое-то окно и затем на каждом игровом шаге он перепрыгивает в какое-то другое окно — так до тех пор, пока не отыщет бомбу.

Инциализация

В первой строке заданы числа W и H — соответственно количество окон на каждом этаже (оно для всех этажей одно и то же) и количество этажей в здании.

Во второй строке задано количество переходов, которые Бэтмен может сделать до взрыва. Это число нам не понадобится.

В третьей строке заданы два целых числа — x и y — координаты окна, с которого Бэтмен начинает свой поиск. Первая координата задаёт номер окна на этаже (начиная с нуля), вторая — номер этажа (также начиная с нуля). Нулевой этаж — верхний, нулевое окно на каждом этаже — левое.

Входные данные для одного игрового хода

Одна строка DIR, задающая направление, в котором следует искать бобму:

Выходные данные для одного игрового хода

Одна строка, в которой заданы два целых числа, разделённых одним пробелом, — координаты окна, которое должен проверить Бэтмен.

Решение

Игровой цикл продолжается до тех пор, пока либо бобма взорвётся, либо Бэтмен её обезвредит. Т.е. либо нам не хватит шагов, либо мы угадаем обе координаты. На каждом шаге игрового цикла будем перемещать Бэтмена с учётом направления, в котором находится бомба, и при этом «сжимать» область игрового поля, в которой он может прыгать. Однажды этот промежуток ужмётся в ондну точку — ту самую, абсцисса которой соответствует координате бомбы.

Обозначим координаты бобмы через BX и BY и введём четыре вспомогательных параметра: l, r, u, b — «динамические границы», левая, правая, верхняя и нижняя соответственно. Идея состоит в том, чтобы на каждом шаге выполнялись неравенства [latex] l \leq BX \leq r [/latex] и [latex] d \leq By \leq u [/latex].

Зададим начальные значения [latex] l = 0 [/latex], [latex] r = W — 1 [/latex], [latex] u = 0 [/latex] и [latex] d = H — 1 [/latex]. Тогда после инициализации игры указанные выше неравенства справедливы тривиальным образом (это просто заданные по условию ограничения на возможные значения Bx и By). Переходим к первому ходу, он же первый шаг игрового цикла. Мы считали строку DIR, указавшую нам направление, в котором следует искать бомбу.

Для оси абсцисс имеет место один из трёх случаев:

[latex] BX < x [/latex] (если DIR — одна из строк «L», «DL», «UL»). В этом случае справедливо неравенство [latex] l \leq BX \leq x — 1 [/latex]. Положим [latex] r = x — 1 [/latex]. Тогда будет справедливо неравенство [latex] l \leq BX \leq r [/latex]. Отметим, что новый промежуток [latex] l \ldots r [/latex] в этом случае будет на единицу короче предыдущего.
[latex] BX = x [/latex] (если DIR — одна из строк «U» и «B»). В этом случае всё хорошо.
[latex] BX > x [/latex] (если DIR — одна из строк «R», «DR», «UR»). В этом случае справедливо неравенство [latex] x + 1 \leq BX \leq r [/latex]. Положим [latex] l = x + 1 [/latex]. Тогда будет справедливо неравенство [latex] l \leq BX \leq r [/latex]. Отметим, что новый промежуток [latex] l \ldots r [/latex] в этом случае будет на единицу короче предыдущего.

Если [latex] BX = x [/latex], то всё хорошо — мы уже знаем абсциссу бомбы. А что делать в остальных двух случаях? Как эффективнее искать бомбу? Можно просматривать все значения из промежутка [latex] l \ldots r [/latex] поочерёдно слева направо, но что если бомба расположена у правого края? Можно просматривать все значения поочерёдно справа налево, но что если координата бомбы равна l, а промежуток большой? Остаётся один естественный вариант — «прыгнуть» в середину промежутка, т.е. в точку с абсциссой [latex] \left \lfloor \frac{l + r}{2} \right \rfloor[/latex]. На следующем шаге цикла надо повторить приведённые выше рассуждения, изменения границ и «прыжок». Таким образом, либо мы случайно наткнётся на абсциссу бомбы, либо промежуток [latex] l .. r [/latex], уменьшаясь каждый раз на одно число, ужмётся в точку, т.е. мы тоже найдём абсциссу бомбы! Осталось применить те же рассуждения к ординате бомбы. Надеюсь, код ответит на оставшиеся вопросы.

Код

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int W, H;   // Количество окон по горизонтали и вертикали соответственно
    cin >> W >> H; cin.ignore();
    int l = 0, r = W - 1, u = 0, d = H - 1; // Начальные значения границ
    int N;
    cin >> N; cin.ignore();
    int x, y;
    cin >> x >> y; cin.ignore();

    // Игровой цикл
    while (1) {
        string DIR; // Направление, в котором находится бомба
        cin >> DIR;
        if ((DIR[0] == 'L')  ||  (DIR[1] == 'L'))
            r = x - 1;
        if ((DIR[0] == 'R')  ||  (DIR[1] == 'R'))
            l = x + 1;
        if (DIR[0] == 'U')
            d = y - 1;
        if (DIR[0] == 'D')
            u = y + 1;
        
        x = (l + r)/2;  // Абсцисса нового окна
        y = (u + d)/2;  // Ордината нового окна
        
        cout << x << " " << y << endl;
    }
}

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

int main()

{

int W, H; // Количество окон по горизонтали и вертикали соответственно

cin >> W >> H; cin.ignore();

int l = 0, r = W - 1, u = 0, d = H - 1; // Начальные значения границ

int N;

cin >> N; cin.ignore();

int x, y;

cin >> x >> y; cin.ignore();

// Игровой цикл

while (1) {

string DIR; // Направление, в котором находится бомба

cin >> DIR;

if ((DIR[0] == 'L') || (DIR[1] == 'L'))

r = x - 1;

if ((DIR[0] == 'R') || (DIR[1] == 'R'))

l = x + 1;

if (DIR[0] == 'U')

d = y - 1;

if (DIR[0] == 'D')

u = y + 1;

x = (l + r)/2; // Абсцисса нового окна

y = (u + d)/2; // Ордината нового окна

cout << x << " " << y << endl;

}

Код на Java

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        int w = in.nextInt(), h = in.nextInt();
        int l = 0, r = w-1, u = 0, d = h-1;
        int n = in.nextInt(), x = in.nextInt(), y = in.nextInt();
        
        while (true) {
            char dir = in.next().charAt(0);
            if ((dir == 'L') || (dir == 'L'))
                r = x-1;
            if ((dir == 'R') || (dir == 'R'))
                l = x+1;
            if (dir == 'U')
                d = y-1;
            if (dir == 'D')
                u = y+1;
            x = (l + r) / 2;
            y = (u + d) / 2;
            System.out.println(x + " " + y);
        }
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

int w = in.nextInt(), h = in.nextInt();

int l = 0, r = w-1, u = 0, d = h-1;

int n = in.nextInt(), x = in.nextInt(), y = in.nextInt();

while (true) {

char dir = in.next().charAt(0);

if ((dir == 'L') || (dir == 'L'))

r = x-1;

if ((dir == 'R') || (dir == 'R'))

l = x+1;

if (dir == 'U')

d = y-1;

if (dir == 'D')

u = y+1;

x = (l + r) / 2;

y = (u + d) / 2;

System.out.println(x + " " + y);

}

Подтверждение

Heat Detector

Related Images:

Temperatures

14/10/2014 by Вустянюк Ігор Дмитрович

Задача взята с сайта codingame.com

Задача.

Задан набор целых чисел (значения температуры за различные моменты времени). Нужно вывести из них ближайшее к нулю.

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

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

Вывести нуль, если [latex] N = 0[/latex]. В противном случае вывести число, ближайшее к нулю, причём если два числа разных знаков одинаково близки к нулю, нужно вывести положительное.

Решение.

Сначала отфильтруем случай, когда [latex] N = 0[/latex]. В этом случае, как от нас и требуют, напечатаем нуль.

Если же [latex] N > 0 [/latex], прибегнем к уже знакомому нам приёму. Введём новую переменную — min — и присвоим ей первое число. Затем в цикле for будем эту переменную менять, если наткнёмся число, более близкое к нулю, чем хранящееся в min. Вот основной вопрос: когда нам нужно менять min? «Число [latex] a [/latex] ближе к нулю, чем число [latex] b [/latex]» означает, что [latex] a [/latex] по модулю меньше, чем [latex] b [/latex]. Значит, если число, прочитанное на текущем шаге цикла, по модулю строго меньше, чем число, хранящееся в min, переменную min нужно обновить. Но есть ещё один случай, когда переменную min следует обновить — это тот случай, когда текущее число положительно и столь же близко к нулю, как и число, хранящееся в min. Это действие даёт нам гарантию того, что если два числа разных знаков одинаково близки к нулю, будет выведено положительное.

Код на С++

#include <iostream>
#include <string>
#include <math.h>
using namespace std;

int main()
{
	int N;
	cin >> N;
	if (N == 0)
        cout << 0 << endl;
    else {
        int min, temp;
        cin >> min;
        for (int i = 1; i < N; i++) {
            cin >> temp;
            if ((abs(temp) < abs(min)) || (temp == abs(min)))
                min = temp;
	    }
	    cout << min;
    }
	return 0;
}

#include <iostream>

#include <string>

#include <math.h>

using namespace std;

int main()

{

int N;

cin >> N;

if (N == 0)

cout << 0 << endl;

else {

int min, temp;

cin >> min;

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

cin >> temp;

if ((abs(temp) < abs(min)) || (temp == abs(min)))

min = temp;

}

cout << min;

}

return 0;

}

Код на Java

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int N = in.nextInt();
		if (N == 0)
			System.out.println(0);
		else {
			int min = in.nextInt(), temp;
			for (int i = 1; i < N; i++) {
				temp = in.nextInt();
				if ((Math.abs(temp) < Math.abs(min)) || (temp == Math.abs(min)))
					min = temp;
			}
			System.out.println(min);
		}
	}
}