Category Archives: F. Динамическое программирование

Задачи связанные с применением приёмов динамического программирования при оптимизации.

Динамическое программирование

Опубликовано: 26/04/2017

Для решение оптимизационных задач методами динамического программирования характерны два важных момента — меморизация и принцип оптимальности подзадач. Меморизация состоит в запоминании результатов решения подзадач, чтобы мгновенно решать их если они снова встретятся. Принцип оптимальности подзадач состоит в сведении исходной задачи к некоторому числу подзадач меньшей размерности. Обычно это продолжается до тех пор, пока решение не … Continue reading →

Опубликованные решения

e-olymp 1619. Ограбление домов

23/06/2021 by Oleksandr.Ivanov

Задача

Вы – профессионал своего дела и планируете ограбить ряд домов вдоль улицы. В каждом доме спрятана определенная сумма денег. Единственное, что мешает Вам грабить – так это то, что соседние дома связаны системой безопасности: будет передан сигнал в полицию, если два соседние дома будут ограблены в один и тот же вечер.

Зная количество денег в каждом доме, определите максимальную сумму, которую Вы сможете ограбить сегодня вечером без уведомления полиции.

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

Первая строка содержит количество домов $n (1 \leqslant n \leqslant 10^6)$. Вторая строка содержит n целых неотрицательных чисел $a_1, a_2, …, a_n$, где $a_i$ — количество денег, которое может быть вынесено из iго дома.

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

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

Тесты

№	Входные данные	Выходные данные
1	5 6 1 2 10 4	16
2	10 4 1 29 0 14 8 31 12 7 5	85
3	2 1 3	3

Код

#include <iostream>
 
using namespace std;
 
void houseRobbery(int houseCount, unsigned long *maxSum, unsigned long *initialHouses) {
    /*
    A function that, through dynamic programming, calculates the maximum production of houses not standing nearby.
    The function does not return anything, since it modifies arrays through pointers
    */
    
    // Initial state values from first two houses
    maxSum[0] = initialHouses[0];
    maxSum[1] = max(initialHouses[0], initialHouses[1]);
 
    // Since by condition it is given that we cannot rob two houses in a row, 
    // then we will take the maximum house of two: maxSum[i - 1] and maxSum[i - 2] + initialHouses[house] 
    // (where initialHouses[house] is the amount of money in the i-th house)
    for (int house = 2; house < houseCount; house += 1) {
        maxSum[house] = max(maxSum[house - 1], maxSum[house - 2] + initialHouses[house]);
    }
}
 
int main() {
    int houseCount;
    cin >> houseCount;

    // Initialize the arrays not containing negative values
    unsigned long initialHouses[houseCount], maxSum[houseCount];
 
    // Filling the initial array of houses with user input
    for (int element = 0; element < houseCount; element += 1) {
        cin >> initialHouses[element];
    }
    
    // Calling the function
    houseRobbery(houseCount, maxSum, initialHouses);
 
    cout << maxSum[houseCount - 1];
    return 0;
}

#include <iostream>

using namespace std;

void houseRobbery(int houseCount, unsigned long *maxSum, unsigned long *initialHouses) {

A function that, through dynamic programming, calculates the maximum production of houses not standing nearby.

The function does not return anything, since it modifies arrays through pointers

// Initial state values from first two houses

maxSum[0] = initialHouses[0];

maxSum[1] = max(initialHouses[0], initialHouses[1]);

// Since by condition it is given that we cannot rob two houses in a row,

// then we will take the maximum house of two: maxSum[i - 1] and maxSum[i - 2] + initialHouses[house]

// (where initialHouses[house] is the amount of money in the i-th house)

for (int house = 2; house < houseCount; house += 1) {

maxSum[house] = max(maxSum[house - 1], maxSum[house - 2] + initialHouses[house]);

}

int main() {

int houseCount;

cin >> houseCount;

// Initialize the arrays not containing negative values

unsigned long initialHouses[houseCount], maxSum[houseCount];

// Filling the initial array of houses with user input

for (int element = 0; element < houseCount; element += 1) {

cin >> initialHouses[element];

}

// Calling the function

houseRobbery(houseCount, maxSum, initialHouses);

cout << maxSum[houseCount - 1];

return 0;

}

Решение

Данная задача, это типичный пример применения динамического программирования.
Динамическое программирование — это метод решения задачи путём её разбиения на несколько одинаковых подзадач, рекуррентно связанных между собой.

Решение задачи динамическим программированием должно содержать следующее:
— Значение начальных состояний. В результате долгого разбиения на подзадачи вам необходимо свести функцию либо к уже известным значениям, либо к задаче, решаемой элементарно.
— Зависимость элементов динамики друг от друга. Такая зависимость может быть прямо дана в условии. В противном случае вы можете попытаться узнать какой-то известный числовой ряд, вычислив первые несколько значений вручную.

Для решения данной задачи будет использовать метод последовательного вычисления (далее МПВ).
МПВ подходит, только если функция ссылается исключительно на элементы перед ней — это его основной минус.
Суть метода в следующем: необходимо создать массив на N элементов и последовательно заполнять его значениями. Таким образом вычисляется, в том числе те значения, которые для ответа не нужны. В значительной части задач на динамику этот факт можно опустить, так как для ответа часто бывают нужны как раз все значения.

Зная, что такое динамическое программирование и МПВ — можно описать алгоритм решения.
Пусть $a_i$ — количество денег в $i$-ом доме и houseRobbery(i) — максимальное количество денег, которое удалось унести грабителю.

Следовательно, значения начальных состояний будут такими:
— Для первого дома — количество денег в нем.
— Для второго — максимальное количество денег из первых двух домов.

Далее в цикле рассматривается $i$-й дом и определять для него $houseRobbery(i)$, где houseRobbery(i) — максимальное из houseRobbery(i - 1) и houseRobbery(i - 2) + initialHouses[i], так как нужно учитывать houseRobbery(i - 1), если $i$-й дом не был ограблен, а houseRobbery(i - 2) + initialHouses[i], если $i$-й дом — ограблен.

И так как используется МПВ, то последний элемент в заведенном массиве и будет решением этой задачи.

Ссылки

Related Images:

e-olymp 7824. Без повторений

22/12/2020 by Максим Алексеев

Задача

В натуральном числе $A$ удалили некоторые цифры так, чтобы получить наибольшее натуральное число $B$ с разными цифрами. Какое это число?

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

Натуральное число $x \ (1 \leqslant x \leqslant 10^{100})$.

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

Натуральное число $B$.

Тесты

№	Входные данные	Выходные данные
1	575747	754
2	123231	321
3	314159265359	4192653
4	1092010	9210
5	112221332	213

Код

#include <iostream>
#include <cstring>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
 
int main() {
    string current_number;
    string ansver = "";
    cin >> current_number;
    set<char> digits_set;    // Инициализируем и заполняем множество со всеми цифрами начального числа
    for (int i = 0; i < current_number.size(); i++){
        char element = current_number[i];
        digits_set.insert(element);
    }
    std::vector<char> digits;
    for (char i : digits_set){
        digits.push_back(i);
    }
    std::reverse(digits.begin(), digits.end());    // Располагаем цифры в порядке убывания
    while (digits.size() != 1){    // Повторяем, пока не нашли все цифры кроме последней
        for (int i=0; i < digits.size(); i++){    // Перебираем цифры в порядке убывания
            char local_max = digits[i];
            int position = current_number.find(local_max);
            string new_number;
            for (int j = position; j < current_number.size(); j++){    // Делаем срез по элементу
                new_number += current_number[j];
            }
            set<char> digits_on_the_right;
            for (int j = 0; j < new_number.size(); j++){    // Находим цифры нового числа
                digits_on_the_right.insert(new_number[j]);
            }
            if (digits.size() == digits_on_the_right.size()){    // Проверяем, сохранится ли ранг ответа
                ansver += local_max;
                digits.erase(digits.begin() + i);
                string number_without_digit = "";
                for (int t = 0; t < new_number.size(); t++){    // Удаляем добавленную в ответ цифру из числа
                    if (new_number[t] != local_max){
                        number_without_digit += new_number[t];
                    }
                }
                current_number = number_without_digit;
                break;    // Останавливаем цикл, т.к. необходимая цифра на позицию уже найдена
            }
        }
    }
    cout << ansver + digits[0];    // Добавляем к ответу последнюю оставшуюся цифру
    return 0;
}

#include <iostream>

#include <cstring>

#include <set>

#include <vector>

#include <algorithm>

using namespace std;

int main() {

string current_number;

string ansver = "";

cin >> current_number;

set<char> digits_set; // Инициализируем и заполняем множество со всеми цифрами начального числа

for (int i = 0; i < current_number.size(); i++){

char element = current_number[i];

digits_set.insert(element);

}

std::vector<char> digits;

for (char i : digits_set){

digits.push_back(i);

}

std::reverse(digits.begin(), digits.end()); // Располагаем цифры в порядке убывания

while (digits.size() != 1){ // Повторяем, пока не нашли все цифры кроме последней

for (int i=0; i < digits.size(); i++){ // Перебираем цифры в порядке убывания

char local_max = digits[i];

int position = current_number.find(local_max);

string new_number;

for (int j = position; j < current_number.size(); j++){ // Делаем срез по элементу

new_number += current_number[j];

}

set<char> digits_on_the_right;

for (int j = 0; j < new_number.size(); j++){ // Находим цифры нового числа

digits_on_the_right.insert(new_number[j]);

}

if (digits.size() == digits_on_the_right.size()){ // Проверяем, сохранится ли ранг ответа

ansver += local_max;

digits.erase(digits.begin() + i);

string number_without_digit = "";

for (int t = 0; t < new_number.size(); t++){ // Удаляем добавленную в ответ цифру из числа

if (new_number[t] != local_max){

number_without_digit += new_number[t];

}

current_number = number_without_digit;

break; // Останавливаем цикл, т.к. необходимая цифра на позицию уже найдена

}

cout << ansver + digits[0]; // Добавляем к ответу последнюю оставшуюся цифру

return 0;

}

Нажмите здесь, чтобы выполнить этот код.

Решение

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

Рассмотрим пример: для числа $121323$ правильным ответом будет $213$.

Ход рассуждений следующий: поскольку в числе содержатся три цифры, ответ также будет трехзначным. Наибольшая цифра в числе — 3, следовательно, она должна быть первой цифрой ответа. Для выполнения этого условия придется «вычеркнуть» все предыдущие цифры, но тогда мы сможем получить лишь двухзначное число $32$. Следующим кандидатом является двойка, и этот выбор нас полностью устраивает, поскольку справа от нее есть остальные цифры «входного» числа. Записав в ответ $2$, рассмотрим число за ней: $1323$. Мы можем видеть, что двойка повторяется, однако в ответе ее быть уже не может по условию задачи. Отбросим ее за ненадобностью и рассмотрим получившееся число $133$. Для полученного числа нам необходимо выполнить те же операции, что и для предыдущего, а значит, мы столкнулись с задачей на динамическое программирование (о чем нам, правда, уже заботливо сообщил e-olymp прямо под условием). Рассуждения аналогичны: взять $3$ мы не можем, поскольку это вынудит нас отбросить $1$, что в результате даст нам число $23$, то есть даже меньшее, чем то, что мы получали в начале. Следовательно, добавляем к ответу $1$. Последнюю оставшуюся цифру можно сразу добавлять к ответу, поскольку сравнивать ее не с чем. Получаем искомый ответ — $213$.

Как и оговаривалось вначале, работать будем со строчным представлением числа. До объявления цикла в строке 22 выполняются подготовительные процедуры: создается множество с целью определения цифр, составляющих число, а затем массив, в который помещаются элементы множества в порядке убывания. В теле цикла проходим по всем элементам массива, пока не находим такой, справа от которого будут все остальные элементы. Здесь важно отметить две вещи: во-первых, меня не интересуют сами цифры, имеет значение лишь их количество в соответствующих множествах; во-вторых, поскольку справа от элемента могут находится ему идентичные, включаем его в срез строки и проверяем, можно ли опустить левую часть числа без ущерба количеству цифр в нем. Если да, то этот элемент добавляется в ответ и извлекается из массива для следующего прохода, а если нет — программа переходит к следующему по старшинству элементу.

Ссылки

Код на ideone
Задача на e-olymp
Засчитанное решение на e-olymp

Related Images:

e-olymp 7213. Шашка на кубе

12/12/2020 by Максим Ливитчук

Условие

Поверхность куба отрезками, параллельными рёбрам куба, разделена на квадратные клетки, длина сторон которых в $l$ (нечетное натуральное число) раз меньше длины ребра куба. Шашку передвигают за один ход из клетки на произвольную смежную с ней клетку (что имеет с данной общую сторону).

Создайте программу, которая вычислит, сколькими различными способами шашка может попасть за $m$ ходов из клетки в центре одной грани на клетку, расположенную в центре смежной грани.

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

Содержит натуральные числа $l$ и $m$ ($l < 52$, $m < 200$).

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

Вывести искомое количество способов.

Тесты

l	m	вывод
3	3	1
3	4	0
3	5	25
51	199	4009263689513240276071196173369495212494629453793821392879244551766927964742684514532573281589075237363501397360
3	199	11954860546705755218324706261555627152268568460810054501274297031890136116190373877274924800908756150285132065690107399

Код

#include <iostream>
#include <iomanip>
#include <vector>
using namespace std;

#define cr(a, b, x, y) case a: return CellCoord{b, x, y}
#define SIDENUM 3 //количество сторон куба которые хранятся
#define MAX_L 51 //максимальное значение L

#define BASE 1000000000 //10^9, основание системы счисления для длинной арифметики 
#define DNUM 9 //количество цифр 10-ичной системы счисления в 1 "цифре" длинной арифметики

struct LongNum {
    //реализация длинной арифметики на векторах со сложением и выводом
    vector<int> v;
    LongNum() {} //стандартный конструктор
    LongNum(int s) { //конструктор из int
        v.push_back(s);
    }
    void print() { //вывод числа
        cout <<(v.empty() ? 0 : v.back());
        for (int i = (int)v.size() - 2; i>=0; i--)
            cout <<setfill('0') <<setw(DNUM) <<v[i];
    }
    void add(LongNum term) { //прибавление длинного числа
        auto b = term.v;
        int carry = 0;
        for (size_t i = 0; i < max(v.size(), b.size()) || carry; i++) {
            if (i == v.size())
                v.push_back(0);
            v[i] += carry + (i < b.size() ? b[i] : 0);
            carry = v[i] >= BASE;
            if (carry)  v[i] -= BASE;
        }
    }
};

struct CellCoord {
    //хранит данные о положении клетки
    short side;
    short x, y;
};

struct CellNeighbors {
    //хранит данные о положении всех(4) соседей определённой клетки
    CellCoord n[4];
};

CellCoord FixNeighbor(short l, short side, short x, short y) {
    //исправляет данные о положении клетки, если она выходит за края грани
    if(x == -1) { //если сосед находится левее грани
        switch(side) {
        //если координаты выходят за левую границу 0-ой грани - меняет грань на 1-ую,
        //обнуляя y, а в x записывает старый y 
        cr(0, 1, y,     0); //и так далее
        cr(1, 1, l-1,   y);
        cr(2, 1, l-y-1, l-1);
        }
    } else if(x == l) {//правее
        switch(side) {
        cr(0, 1, l-y-1, 0);
        cr(1, 1, 0,     y);
        cr(2, 1, y,     l-1);
        }
    } else if(y == -1) {//выше
        switch(side) {
        cr(0, 1, l-x-1, 0);
        cr(1, 0, x,     l-1);
        cr(2, 1, x,     l-1);
        }
    } else if(y == l) {//ниже
        switch(side) {
        cr(0, 1, x,     0);
        cr(1, 2, x,     0);
        cr(2, 1, l-x-1, l-1);
        }
    } else {
        // если координаты не вышли за границы грани просто возвращаем неизменёные координаты
        return CellCoord{side, x, y};
    }
}

CellNeighbors GetNeighbors(short l, short side, short x, short y) {
    //возвращает исправленные координаты всех(4) соседних клеток
    return CellNeighbors{{
        FixNeighbor(l, side, x-1, y),
        FixNeighbor(l, side, x+1, y),
        FixNeighbor(l, side, x, y-1),
        FixNeighbor(l, side, x, y+1)
    }};
}

int main() {
    short l, m;
    bool flag = false;
    cin >>l >>m;
    LongNum cubes[2][SIDENUM][MAX_L][MAX_L];

    cubes[0][0][l/2][l/2] = LongNum(1);
    //за 0 ходов можно дойти 1 путём в изначальную точку

    CellNeighbors nbs[SIDENUM][MAX_L][MAX_L];
    //массив координат соседей

    for(short side=0; side<SIDENUM; side++) {
        for(short xi=0; xi<l; xi++) {
            for(short yi=0; yi<l; yi++) { //перебор координат всех клеток
                nbs[side][xi][yi] = GetNeighbors(l, side, xi, yi);
                //кэш координат соседних клеток
            }
        }
    }

    for(short i=0; i<m; i++) {
        for(short side=0; side<SIDENUM; side++) {
            for(short xi=0; xi<l; xi++) {
                for(short yi=0; yi<l; yi++) { //перебор всех клеток
                    LongNum neighbor_sum;
                    for(auto e: nbs[side][xi][yi].n) { //перебор всех соседей
                        neighbor_sum.add(cubes[flag][e.side][e.x][e.y]);
                        //сложение количества путей ко всем соседям на предыдущем шаге
                    }
                    cubes[!flag][side][xi][yi] = neighbor_sum;
                    //запись получившейся суммы в клетку
                }
            }
        }
        flag = !flag; //замена местами массива для предыдущего шага и нынешнего
    }
    cubes[flag][1][l/2][l/2].print();
    //вывод количества путей к центру соседней грани на m-ом шаге
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

#include <iostream>

#include <iomanip>

#include <vector>

using namespace std;

#define cr(a, b, x, y) case a: return CellCoord{b, x, y}

#define SIDENUM 3 //количество сторон куба которые хранятся

#define MAX_L 51 //максимальное значение L

#define BASE 1000000000 //10^9, основание системы счисления для длинной арифметики

#define DNUM 9 //количество цифр 10-ичной системы счисления в 1 "цифре" длинной арифметики

struct LongNum {

//реализация длинной арифметики на векторах со сложением и выводом

vector<int> v;

LongNum() {} //стандартный конструктор

LongNum(int s) { //конструктор из int

v.push_back(s);

}

void print() { //вывод числа

cout <<(v.empty() ? 0 : v.back());

for (int i = (int)v.size() - 2; i>=0; i--)

cout <<setfill('0') <<setw(DNUM) <<v[i];

}

void add(LongNum term) { //прибавление длинного числа

auto b = term.v;

int carry = 0;

for (size_t i = 0; i < max(v.size(), b.size()) || carry; i++) {

if (i == v.size())

v.push_back(0);

v[i] += carry + (i < b.size() ? b[i] : 0);

carry = v[i] >= BASE;

if (carry) v[i] -= BASE;

}

};

struct CellCoord {

//хранит данные о положении клетки

short side;

short x, y;

};

struct CellNeighbors {

//хранит данные о положении всех(4) соседей определённой клетки

CellCoord n[4];

};

CellCoord FixNeighbor(short l, short side, short x, short y) {

//исправляет данные о положении клетки, если она выходит за края грани

if(x == -1) { //если сосед находится левее грани

switch(side) {

//если координаты выходят за левую границу 0-ой грани - меняет грань на 1-ую,

//обнуляя y, а в x записывает старый y

cr(0, 1, y, 0); //и так далее

cr(1, 1, l-1, y);

cr(2, 1, l-y-1, l-1);

}

} else if(x == l) {//правее

switch(side) {

cr(0, 1, l-y-1, 0);

cr(1, 1, 0, y);

cr(2, 1, y, l-1);

}

} else if(y == -1) {//выше

switch(side) {

cr(0, 1, l-x-1, 0);

cr(1, 0, x, l-1);

cr(2, 1, x, l-1);

}

} else if(y == l) {//ниже

switch(side) {

cr(0, 1, x, 0);

cr(1, 2, x, 0);

cr(2, 1, l-x-1, l-1);

}

} else {

// если координаты не вышли за границы грани просто возвращаем неизменёные координаты

return CellCoord{side, x, y};

}

CellNeighbors GetNeighbors(short l, short side, short x, short y) {

//возвращает исправленные координаты всех(4) соседних клеток

return CellNeighbors{{

FixNeighbor(l, side, x-1, y),

FixNeighbor(l, side, x+1, y),

FixNeighbor(l, side, x, y-1),

FixNeighbor(l, side, x, y+1)

}};

}

int main() {

short l, m;

bool flag = false;

cin >>l >>m;

LongNum cubes[2][SIDENUM][MAX_L][MAX_L];

cubes[0][0][l/2][l/2] = LongNum(1);

//за 0 ходов можно дойти 1 путём в изначальную точку

CellNeighbors nbs[SIDENUM][MAX_L][MAX_L];

//массив координат соседей

for(short side=0; side<SIDENUM; side++) {

for(short xi=0; xi<l; xi++) {

for(short yi=0; yi<l; yi++) { //перебор координат всех клеток

nbs[side][xi][yi] = GetNeighbors(l, side, xi, yi);

//кэш координат соседних клеток

}

for(short i=0; i<m; i++) {

for(short side=0; side<SIDENUM; side++) {

for(short xi=0; xi<l; xi++) {

for(short yi=0; yi<l; yi++) { //перебор всех клеток

LongNum neighbor_sum;

for(auto e: nbs[side][xi][yi].n) { //перебор всех соседей

neighbor_sum.add(cubes[flag][e.side][e.x][e.y]);

//сложение количества путей ко всем соседям на предыдущем шаге

}

cubes[!flag][side][xi][yi] = neighbor_sum;

//запись получившейся суммы в клетку

}

flag = !flag; //замена местами массива для предыдущего шага и нынешнего

}

cubes[flag][1][l/2][l/2].print();

//вывод количества путей к центру соседней грани на m-ом шаге

}

Решение

Из условия можно понять, что задача про специфического вида граф, по которому движется шашка. Его вершинами являются клетки на гранях куба, а дуги лежат между клетками с общими границами. Очевидно количество путей за $m$ шагов до любой точки в графе будет равняться сумме количества путей за $m-1$ шагов ко всем соседним вершинам, то есть мы можем получать решение задачи для $m$ шагов из решения меньшей задачи для $m-1$ шагов, из чего можно понять что это задача на динамическое программирование.
Для решения создадим массив со всеми вершинами и будем хранить в нём количество путей к каждой из них на i-ом шаге. Удобнее всего задать такой массив как 6 числовых матриц размером $ l \times l$, по одной на каждую грань куба.

Раскладка шести граней куба с переходами между границами

Соседство будем определять, прибавляя или отнимая единицу от одной из координат клетки в матрице, например $(x-1, y)$ всегда будет соседом $(x, y)$, не считая крайних случаев, когда $x-1$ будет меньше нуля. Такие ситуации в коде обрабатывает функция FixNeighbor(...), в которой прописаны все подобные крайние случаи.

Если посмотреть на правильный ответ к пятому примеру, становится видно, что на больших значениях ответы на тесты превышают все стандартные целочисленные типы данных, поэтому для полного решения необходимо использовать длинную арифметику. В программе она реализована в виде структуры LongNum, логика работы которой взята отсюда.

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

Оптимизированный вариант хранения куба

Так как для получения значения клетки через $i$ шагов нужны значения всех её соседей через $i-1$ шагов, а для получения значения соседей через $i$ шагов нужно значение клетки через $i-1$ шагов, нам не хватит только одного массива для перезаписи, надо использовать минимум два для хранения предыдущего и нынешнего состояния. В программе это реализовано с помощью булевой переменной flag — сначала мы вычисляем следующее состояние на основании 0-ого массива ( flag), записывая результат 1-ый ( !flag), а потом инвертируем значение переменной на противоположное и массивы в алгоритме меняются местами.

Ссылки

Related Images:

e-olymp 399. Последствия гриппа в Простоквашино

19/05/2020 by Никита Репнин

Задача

”Дорогой дядя Фёдор!

После того, как мама испугалась, что ты можешь заболеть какой-то нечеловеческой болезнью и забрала тебя в город, Шарик видимо все-таки чем-то заболел, ибо его поступки я уже иначе объяснить не могу, как последствиями постоянного общения с Хрюшей.

Суди сам: он сначала распилил шахматную доску на квадратики, потом на каждый квадратик наклеил изображение круглой скобки и, выдав определенное количество квадратиков, заставляет меня считать, сколько разных правильных скобочных последовательностей я смогу построить из имеющегося у меня числа квадратиков. При этом он еще и требует, чтобы я использовал все квадратики!

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

Дядя Фёдор, если тебе не трудно, напиши мне программу для подсчета этого количества, ибо из-за того, что Шарик задает мне свою непонятную задачу до 20 раз на день, у меня даже не остается времени ухаживать за моей любимой коровой.

Всегда твой верный друг – кот Матроскин.”

Помогите дяде Фёдору написать программу для Матроскина, иначе тот может остаться без молока.

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

В первой строке задано число $n$ – количество заданий Шарика за день. В следующих $n$ строках задано по одному числу $k$ – количество выданных в очередной раз Матроскину квадратиков с изображением скобок. Квадратики Матроскин может переворачивать, получая при этом как открывающую, так и закрывающую скобку.

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

Вывести в $n$ строках по одному числу – ответ на соответствующее задание Шарика.

Тесты

№	Входные данные	Выходные данные
1	3 2 3 4	1 0 2
2	5 3 11 7 43 27	0 0 0 0 0
3	6 2 28 42 14 64 0	1 2674440 24466267020 429 55534064877048198 1

Код

#include <iostream>
using namespace std;
 
int main() {
    int n, k;
    long long brackets [33];
    brackets [0] = 1;
    for(int i = 1; i <= 32; ++ i){
        brackets [i]=0;
        for(int j = 0; j < i; ++ j){
            brackets [i] += brackets [j] * brackets [i - 1 - j];
        }
    }
    cin >> n;
        for (int i = 0; i < n; i ++) {
        cin >> k;
        cout << (k % 2 == 0 ? brackets [k / 2] : 0) << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, k;

long long brackets [33];

brackets [0] = 1;

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

brackets [i]=0;

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

brackets [i] += brackets [j] * brackets [i - 1 - j];

}

cin >> n;

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

cin >> k;

cout << (k % 2 == 0 ? brackets [k / 2] : 0) << endl;

}

return 0;

}

Решение

Правильную скобочную последовательность можно построить лишь из четного количества скобок, т.е. для нечетного числа ответ заведомо $0$. А для $2m$ скобок ($m$ открывающих и $m$ закрывающих) ответ равен числу Каталана $C_m$. Для вычисления которого используется рекуррентное соотношение: $$C_m=\sum_{i=0}^{m-1} C_i \cdot C_{m-1-i}$$

Задача на e-olymp
Код программы на ideone
Засчитанное решение

Related Images:

e-olimp 8536. Заповнення смуги $3 \times n$

03/05/2020 by Анна Цивинская

Внимание: Задача на сайте e-olymp была заменена на другую. Теперь такой задачи там нет.

Задача

Смугу висотою $3$ см і шириною $n$ см суцільно заповнено прямокутниками $3 \times 1$ та $1 \times 3$ см. Скількома способами можна її заповнити? Різні способи – це різні кількості вказаних прямокутників та їх різні розташування.

Вхідні дані

Одне натуральне число $n$ $(1 \leqslant n \leqslant 50)$.

Вихідні дані

Вивести кількість способів, якими можна заповнити смугу.

Тести

Вхідні дані	Вихідні дані
1	1
5	4
12	60
50	122106097

Код № 1

#include <iostream>
using namespace std;
 
int main() {
   int n;
   cin >> n;
   int F[51] = {0, 1, 1, 2, 3};
   for(int i = 5; i <= n; i++) {
      F[i] = F[i-2] + F[i-3] + F[i-4];
   }
   cout << F[n];
   return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

int F[51] = {0, 1, 1, 2, 3};

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

F[i] = F[i-2] + F[i-3] + F[i-4];

}

cout << F[n];

return 0;

}

Рішення 1

Це завдання на динамічне програмування, тому спочатку нам потрібно розбити цю задачу на декілька простих. Треба порахувати кількість способів для чотирьох перших елементів масиву. Якщо рахувати далі, то ми помітимо, що кожне наступне значення отримується за формулою F[i] = F[i-2] + F[i-3] + F[i-4].

Код № 2

#include <iostream>
using namespace std;
 
int F[51] = {0, 1, 1, 2, 3};
 
int numberOfWays(int n) {
   if(F[n]) {
      return F[n];
   } else {
      F[n] = numberOfWays(n-2) + numberOfWays(n-3) + numberOfWays(n-4);
   }
   return F[n];
}
 
int main() {
   int n;
   cin >> n;
   cout << numberOfWays(n);
   return 0;
}

#include <iostream>

using namespace std;

int F[51] = {0, 1, 1, 2, 3};

int numberOfWays(int n) {

if(F[n]) {

return F[n];

} else {

F[n] = numberOfWays(n-2) + numberOfWays(n-3) + numberOfWays(n-4);

}

return F[n];

}

int main() {

int n;

cin >> n;

cout << numberOfWays(n);

return 0;

}

Рішення 2

Також для рішення цієї задачі можна використати рекурсію. При виклику функції ми перевіряємо, чи є в пам’яті це значення. Якщо такого значення не має, то ми його рахуємо. Таким чином ми уникаємо використання зайвої пам’яті.

Посилання

Умова задачі на E-Olymp
Зараховане рішення № 1 на E-Olymp
Зараховане рішення № 2 на E-Olymp
Код задачі № 1 на Ideone
Код задачі № 2 на Ideone

Related Images:

e-olimp 8234. Сходинки

09/04/2020 by Елизавета Савицкая

Задача

Скількома способами можна потрапити на $n$-ту сходинку, якщо можна ступати на наступну, переступати через одну і через дві сходинки.

Вхідні дані

Одне число $n$ — номер сходинки $(n \leqslant 60)$.

Вихідні дані

Вивести кількість способів, якими можна потрапити на $n$-ту сходинку.

Тести

Вхідні дані	Вихідні дані
0	1
5	13
15	5768
32	181997601
60	4680045560037375

Код № 1

#include <iostream>
using namespace std;

int main() {
   int n;
   cin >> n;
   long long arr[61] = {0};
   arr[0] = 1;
   arr[1] = 1;
   arr[2] = 2;
   for(int i = 3; i <= n; i++) {
      arr[i] = arr[i-1] + arr[i-2] + arr[i-3];
   }
   cout << arr[n];
   return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

long long arr[61] = {0};

arr[0] = 1;

arr[1] = 1;

arr[2] = 2;

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

arr[i] = arr[i-1] + arr[i-2] + arr[i-3];

}

cout << arr[n];

return 0;

}

Рішення

Розіб’ємо задачу на декілька простих. Спочатку розрахуємо кількість способів для однієї сходинки (1 спосіб), потім для двох (2 способи: 0 $\rightarrow$ 1 $\rightarrow$ 2; 0 $\rightarrow$ 2) і також потрібно врахувати випадок, коли кількість сходинок дорівнює нулю (1 спосіб). Далі легко помітити, що кожне наступне значення дорівнює сумі трьох попередніх звідки і отримуємо формулу:
arr[i] = arr[i-1] + arr[i-2] + arr[i-3]
Також цю задачу можна вирішити за допомогою рекурсії. Я використала рекурсію з запам’ятовуванням для того, щоб уникнути переповнення стеку викликів (загальна ідея така: при кожному виклику функції перевіряємо, чи маємо ми вже це значення, і якщо ні, рахуємо його. Таким чином ми будемо використовувати кожне значення лише один раз).

Код № 2

#include <iostream>
using namespace std;

long long arr[61] = {0};

long long num_of_ways(int n) {
   if(arr[n]) {
      return arr[n];
   }
   else {
      arr[n] = num_of_ways(n-1) + num_of_ways(n-2) + num_of_ways(n-3);
   }
   return arr[n];
}
int main() {
   int n;
   cin >> n;
   arr[0] = 1;
   arr[1] = 1;
   arr[2] = 2;
   cout << num_of_ways(n);
   return 0;
}

#include <iostream>

using namespace std;

long long arr[61] = {0};

long long num_of_ways(int n) {

if(arr[n]) {

return arr[n];

}

else {

arr[n] = num_of_ways(n-1) + num_of_ways(n-2) + num_of_ways(n-3);

}

return arr[n];

}

int main() {

int n;

cin >> n;

arr[0] = 1;

arr[1] = 1;

arr[2] = 2;

cout << num_of_ways(n);

return 0;

}

Посилання

Related Images:

e-olymp 236. Триомино

30/03/2020 by Евгений Фищук

Триомино

Сколькими способами можно замостить прямоугольник $2 × n$ триоминошками? Триомино — это геометрическая фигура, составленная из трех квадратов, соединяющихся между собой вдоль полного ребра. Есть только две возможных триоминошки:

Например, замостить прямоугольник $2 × 3$ можно только тремя различными способами. Поскольку ответ может быть достаточно большим, искомое количество способов следует вычислять по модулю $10^6$.

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

Первая строка содержит количество тестов $t$ ($1 \leqslant t \leqslant 100$). Каждая из следующих $t$ строк содержит значение $n$ ($0 < n < 10^9$).

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

Для каждого теста в отдельной строке выведите количество способов, которыми можно замостить прямоугольник $2 × n$. Результат следует выводить по модулю $10^6$.

Тесты

№	Входные данные	Выходные данные
1	3 3 4 6	3 0 11
2	4 12 15 21 9	153 571 7953 41

Код

#include <iostream>
#include <vector>
#define MOD 1000000
typedef long long ll;
using namespace std;

vector<vector<ll>> multiply(vector<vector<ll>> v1) {
    ll x00 = v1[0][0];
    ll x01 = v1[0][1];
    ll x10 = v1[1][0];
    ll x11 = v1[1][1];
    ll res00, res01, res10, res11;
    res00 = ((x00 * x00) % MOD + (x10 * x01) % MOD) % MOD;
    res01 = ((x00 * x01) % MOD + (x01 * x11) % MOD) % MOD;
    res10 = ((x10 * x00) % MOD + (x10 * x11) % MOD) % MOD;
    res11 = ((x10 * x01) % MOD + (x11 * x11) % MOD) % MOD;
    return{ {(res00 + MOD) % MOD, (res01 - MOD) % MOD}, {(res10 + MOD) % MOD, (res11 - MOD) % MOD} };
}
vector<vector<ll>> pow_mod(vector<vector<ll>> v, int p) {

    if (p == 1) return v;
    if ((p % 2) == 0) {
        vector<vector<ll>> vct = (pow_mod(v, p / 2));
        return multiply(vct);
    }
}

int main() {
    int t, n;
    cin >> t;
    for (int i = 0; i < t; i++)
    {
        cin >> n;
        if (n % 3)
        {
            cout << 0 << endl;
        }
        else
        {
            n /= 3;
            int p = 2;
            ll a1 = 1, a2 = 1;
            while (n > 0)
            {
                if (n & 1)
                {
                    vector<vector<ll>> a = { {4,-1},{1,0} };
                    a = pow_mod(a, p / 2);
                    ll tmp1 = a1;
                    ll tmp2 = a2;
                    a1 = (tmp1 * a[0][0]) % MOD + (tmp2 * ((a[0][1] + MOD) % MOD)) % MOD;
                    a2 = (tmp1 * a[1][0]) % MOD + (tmp2 * ((a[1][1] + MOD) % MOD)) % MOD;
                }
                p *= 2;
                n >>= 1;
            }
            cout << a1 % MOD << endl;
        }
    }
    return 0;
}

#include <iostream>

#include <vector>

#define MOD 1000000

typedef long long ll;

using namespace std;

vector<vector<ll>> multiply(vector<vector<ll>> v1) {

ll x00 = v1[0][0];

ll x01 = v1[0][1];

ll x10 = v1[1][0];

ll x11 = v1[1][1];

ll res00, res01, res10, res11;

res00 = ((x00 * x00) % MOD + (x10 * x01) % MOD) % MOD;

res01 = ((x00 * x01) % MOD + (x01 * x11) % MOD) % MOD;

res10 = ((x10 * x00) % MOD + (x10 * x11) % MOD) % MOD;

res11 = ((x10 * x01) % MOD + (x11 * x11) % MOD) % MOD;

return{ {(res00 + MOD) % MOD, (res01 - MOD) % MOD}, {(res10 + MOD) % MOD, (res11 - MOD) % MOD} };

}

vector<vector<ll>> pow_mod(vector<vector<ll>> v, int p) {

if (p == 1) return v;

if ((p % 2) == 0) {

vector<vector<ll>> vct = (pow_mod(v, p / 2));

return multiply(vct);

}

int main() {

int t, n;

cin >> t;

for (int i = 0; i < t; i++)

{

cin >> n;

if (n % 3)

{

cout << 0 << endl;

}

else

{

n /= 3;

int p = 2;

ll a1 = 1, a2 = 1;

while (n > 0)

{

if (n & 1)

{

vector<vector<ll>> a = { {4,-1},{1,0} };

a = pow_mod(a, p / 2);

ll tmp1 = a1;

ll tmp2 = a2;

a1 = (tmp1 * a[0][0]) % MOD + (tmp2 * ((a[0][1] + MOD) % MOD)) % MOD;

a2 = (tmp1 * a[1][0]) % MOD + (tmp2 * ((a[1][1] + MOD) % MOD)) % MOD;

}

p *= 2;

n >>= 1;

}

cout << a1 % MOD << endl;

}

return 0;

}

Решение

Если n нацело не делится на $3$, то выводится ноль,в ином случае данная задача решается через рекуррентную формулу $a_n=4*a_{n-1}-a_{n-2}$. Но из-за слишком больших чисел мы не можем использовать данную формулу просто так, поэтому мы воспользуемся быстрым вычислением членов рекуррентной последовательности через матрицы. Надо умножать матрицу

$\begin{pmatrix}
4&-1 \\
1&0 \\
\end{pmatrix}$ в степени $p$(где $p$ равна двойке в степени номера единицы в двоичной записи числа ${{n}\over{3}}$) на матрицу $\begin{pmatrix}
1\\
1\\
\end{pmatrix}$ каждый раз, когда встречается единица в двоичной записи числа ${{n}\over{3}}$. На выход подается первое число вектора $2 × 1$.

Ссылки

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

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

Related Images:

e-olymp 4020. Культ-орки на лестнице

10/02/2020 by Мария Жаркая

Задача

В Летней Кинематографической Школе пришло время обеда и эльф Коля поспешил в столовую. Однако для того, чтобы попасть в столовую, Коле нужно подняться по длинной лестнице, а на каждой её ступеньке в это время суток стоит по культ-орку. Каждый культ-орк разрешает Коле пройти по своей ступеньке только после того, как Коля запишется на мероприятие, которое этот культ-орк организует. При этом никакие два культ-орка не проводят одно и то же мероприятие, и все мероприятия проходят в разное время.

Коля — честный эльф, и если уж он запишется на какую игру или конкурс, то потом обязательно придёт поучаствовать. Однако Коля хочет потратить как можно меньше времени на развлечения, ведь иначе ему некогда будет дорешивать кинематографические задачки. К счастью, Коле не надо наступать на каждую ступеньку, он может перепрыгнуть через несколько. Коля хочет узнать, какое минимальное количество времени ему придётся распланировать за один проход по лестнице до столовой.

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

В первой строке вводятся два числа $n$ и $k$ $(1 \leqslant n \leqslant 10000, 0 \leqslant k \leqslant 20)$, $n$ — количество ступенек на лестнице, $k$ — максимальное количество ступенек, через которые Коля может перепрыгнуть за один прыжок (то есть, например, на первом шаге Коля может прыгнуть на $(k + 1)$-ую или более низкие ступеньки). Во второй строке вводятся $n$ чисел: $i$-ое число указывает на длительность в минутах того мероприятия, которое проведёт культ-орк, стоящий на $i$-ой ступеньке. Каждое мероприятие не может длиться более $24$ часов. Ступеньки нумеруются снизу вверх, ступенькой номер $n$ считается весь этаж столовой.

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

Выведите одно число — минимальное количество минут, которое Коле придётся распланировать.

Тесты

№	Входные данные	Выходные данные
1	5 2 7 3 9 2 11	14
2	6 1 59 32 4 21 5 1	42
3	10 3 40 55 85 29 158 105 115 281 320 10	144
4	15 4 67 20 85 12 345 9 234 115 190 47 5 17 23 89 130	156
5	4 0 100 20 31 49	200

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

#include <iostream>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    int stairs[n + 1]; int time[n + 1]; // массивы для времени каждого мероприятия и потраченного времени;
    for(int i = 1; i < n + 1; ++i) {
        cin >> stairs[i]; 
        if (i <= k + 1) time[i] = stairs[i];
    }
    time[0] = 0; 
    for(int i = 2; i <= n; ++i) {
        if (i > k + 1) time[i] = time[i - 1] + stairs[i]; // начальный минимум;
        for(int j = 2; j <= k+1; ++j) {
            if (i - j >= 0) time[i] =  min(time[i - j] + stairs[i], time[i]); // выбор минимально затраченного времени;
        }
    }
    cout << time[n];
}

#include <iostream>

using namespace std;

int main() {

int n, k;

cin >> n >> k;

int stairs[n + 1]; int time[n + 1]; // массивы для времени каждого мероприятия и потраченного времени;

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

cin >> stairs[i];

if (i <= k + 1) time[i] = stairs[i];

}

time[0] = 0;

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

if (i > k + 1) time[i] = time[i - 1] + stairs[i]; // начальный минимум;

for(int j = 2; j <= k+1; ++j) {

if (i - j >= 0) time[i] = min(time[i - j] + stairs[i], time[i]); // выбор минимально затраченного времени;

}

cout << time[n];

}

Решение

Для каждой ступеньки будем считать минимальное время, которое она отнимет у эльфа, учитывая сколько ступенек можно пропустить (от $0$ до $k + 1$). То есть будем прыгать со ступенек пониже (если это возможно) и сравнивать значения на каждой. Под значением подразумевается сумма уже найденного значения на более низкой ступеньке и времени, которое отнимет мероприятие $i$-ой ступеньки. Таким образом мы узнаем, какие ступеньки выгодно перепрыгнуть. $0$-я ступенька займет $0$ минут, так как эльф не потратит время. Изначально за минимум на ступеньках до $k + 1$ включительно можно взять время мероприятия соответствующей ступеньки, для остальных — сумму значения предыдущей ступеньки и времени мероприятия данной ступеньки. В случае, если эти значения не минимальные, они заменятся на подходящие.
Ответом будет значение на последней ступеньке, так как к ней будет проложен путь, который «займет» минимум времени эльфа на развлечения.

Ссылки

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

Related Images:

e-olymp 1661. Рюкзак Алладина

29/01/2020 by Валентин Цушко

Условие

Попав в пещеру с сокровищами, наш Алладин не стал брать старую почерневшую лампу. Он кинулся собирать в свой рюкзак золотые монеты и драгоценные камни. Он бы, конечно, взял все, но чудес не бывает — слишком большой вес рюкзак может просто не выдержать.

Много раз он выкладывал одни вещи и на их место помещал другие, пытаясь как можно выше поднять стоимость взятых драгоценностей.

Требуется определить максимальную стоимость груза, который Алладин может поместить в свой рюкзак.

Будем считать, что в пещере имеются предметы $n$ различных типов, количество предметов каждого типа не ограничено. Максимальный вес, который может выдержать рюкзак, равен $w$. Каждый предмет типа $i$ имеет вес $w_{i}$ и стоимость $v_{i}$ $(i = 1, 2, \ldots, n)$.

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

В первой строке содержится два натуральных числа $w$ и $n$ $(1 \leqslant w \leqslant 250, 1 \leqslant n \leqslant 35)$ — максимальный вес предметов в рюкзаке и количество типов предметов. Следующие $n$ строк содержат по два числа $w_{i}$ и $v_{i}$ $(1 \leqslant w_{i} \leqslant 250, 1 \leqslant v_{i} \leqslant 250)$ — вес предмета типа $i$ и его стоимость.

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

Выведите максимальную стоимость груза, вес которого не превышает $w$.

Тесты

№	Входные данные	Выходные данные
1	10 2 5 10 6 19	20
2	250 35 187 100 28 109 245 142 123 83 237 78 36 172 15 248 90 24 181 137 40 233 8 99 231 128 79 132 43 217 156 104 45 191 130 113 105 225 206 5 26 120 26 119 64 138 23 147 19 202 79 54 149 185 158 79 209 88 110 133 235 209 188 230 15 220 107 164 235 137 60 167	4067
3	35 4 20 4 1 2 10 8 7 6	70

Программный код

#include <iostream>
using namespace std;
 
int main()
{
    int w, n;
    const int NegNum = -1;
    cin >> w >> n;
    int WeiCos[n][2], s[w + 1];
    for(int i = 0; i < n; i++){
        for(int j = 0; j < 2; j++){
            cin >> WeiCos[i][j];
        }
    }
    s[0] = 0;
    for(int j = 1; j <= w; j++){
        s[j] = NegNum;
    }
    for(int i = 0; i < n; i++){
        for(int j = WeiCos[i][0]; j <= w; j++){
            if(s[j - WeiCos[i][0]] != NegNum && s[j] < s[j - WeiCos[i][0]] + WeiCos[i][1]){
                s[j] = s[j - WeiCos[i][0]] + WeiCos[i][1];
            }
        }
    }
    int maxS = 0;
    for(int i = 1; i <= w; i++){
        maxS = max(maxS, s[i]);
    }
    cout << maxS;
 
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

int w, n;

const int NegNum = -1;

cin >> w >> n;

int WeiCos[n][2], s[w + 1];

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

for(int j = 0; j < 2; j++){

cin >> WeiCos[i][j];

}

s[0] = 0;

for(int j = 1; j <= w; j++){

s[j] = NegNum;

}

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

for(int j = WeiCos[i][0]; j <= w; j++){

if(s[j - WeiCos[i][0]] != NegNum && s[j] < s[j - WeiCos[i][0]] + WeiCos[i][1]){

s[j] = s[j - WeiCos[i][0]] + WeiCos[i][1];

}

int maxS = 0;

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

maxS = max(maxS, s[i]);

}

cout << maxS;

return 0;

}

Решение

Допустим $w = 9$, $n = 2$, первый предмет $w_{1} = 3$, $n_{1} = 4$, а второй предмет $w_{2} = 2$, $n_{2} = 1$. После того как считаем условие в два одномерных или один двумерный массив (как вам удобнее). Создадим одномерный массив в котором его размер будет равен $w$ и первый элемент будет равен 0, а остальные будут равны минус бесконечности или как в нашем случае (в коде) -1, как показано на (рис. 1). И дальше как показано на (рис. 2) начиная с элемента с номером веса предмета мы прибавляем его стоимость к стоимости предыдущей как показано в коде s[j] = s[j - WeiCos[i][0]] + WeiCos[i][1];, если прошлый не минус бесконечность. И так же со вторым элементом, когда они пересекаются с первым мы их сравниваем и вписываем в массив, больший. И в самом конце проходим заново массив и выбираем самый больший элемент, где бы он ни был как показано на (рис. 3). И таким образом на последних позициях которые равняются весу, будут записаны самые дорогие комбинации, благодаря записи самых дорогих элементов в ячейки.

Ссылки:
Задача на e-olymp
Код на OnlineGDB
Код на Ideone
Засчитанное решение на e-olymp

Related Images:

e-olymp 1704. Умная черепашка

23/01/2020 by Виктория Крачилова

Условие задачи

Имеется клетчатое поле размером $m\times n$. В левом нижнем углу сидит черепашка. Она умеет ходить только вправо или вверх. Перед тем как добраться до правого верхнего угла её заинтересовал вопрос: сколько существует способов добраться из исходной точки до правого верхнего угла?

Черепашка хотя и умная, но сама считать так много пока не умеет. Помогите черепашке найти ответ на свой вопрос.

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

Два натуральных числа $m$ и $n$, не превышающие 30.

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

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

Тесты

№	Ввод	Вывод
1	4 5	10
2	3 14	105
3	11 17	5311735
4	20 21	68923264410
5	30 30	30067266499541040

Код программы (циклы)

#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    if (m > n) swap(n, m);
    long long den = 1, ways = 1; // den - знаменатель, ways - количество способов.
    for (int i = 0; i < m - 1; i++) {
        ways *= n + i;
        if (ways % den == 0) {
            ways /= den;
            den++;
        }
    }
    cout << ways;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, m;

cin >> n >> m;

if (m > n) swap(n, m);

long long den = 1, ways = 1; // den - знаменатель, ways - количество способов.

for (int i = 0; i < m - 1; i++) {

ways *= n + i;

if (ways % den == 0) {

ways /= den;

den++;

}

cout << ways;

return 0;

}

Решение

Для нахождения количества способов, которыми черепашка сможет добраться из левого нижнего угла в правый верхний, мы воспользуемся формулой из комбинаторики: $\frac{\left(n+m-2\right)!}{(n-1)!\times(m-1)!}$. Для того, чтобы избежать больших чисел, делим на наибольший множитель знаменателя (пусть это будет $\left(n-1\right)!$ ). Получаем: $ \frac{n\times(n+1)\times…\times(n+m-2)}{1\times2\times…\times(m-1)}$. Домножаем числитель, пока он не делится на очередной сомножитель знаменателя. Если делится, то делим и переходим к следующему сомножителю знаменателя.

Код программы (динамическое программирование)

#include <iostream>
#define N 30
int main() {
    // Создаем треугольную матрицу для хранения всех ответов
    long *x[N];
    for (int i=0; i < N; ++i) x[i] = new long[i+1];
    // Находим все ответы
    x[0][0] = 1;
    for (int i=1; i < N; ++i) {
        x[i][0] = 1;
        for (int j=1; j < i; ++j) x[i][j] = x[i-1][j] + x[i][j-1];
        x[i][i] = 2 * x[i][i-1];        
    }
    // Проходим все тесты
    int m, n; 
    std::cin >> m >> n;
    std::cout << x[std::max(n,m)-1][std::min(n,m)-1];
}

#include <iostream>

#define N 30

int main() {

// Создаем треугольную матрицу для хранения всех ответов

long *x[N];

for (int i=0; i < N; ++i) x[i] = new long[i+1];

// Находим все ответы

x[0][0] = 1;

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

x[i][0] = 1;

for (int j=1; j < i; ++j) x[i][j] = x[i-1][j] + x[i][j-1];

x[i][i] = 2 * x[i][i-1];

}

// Проходим все тесты

int m, n;

std::cin >> m >> n;

std::cout << x[std::max(n,m)-1][std::min(n,m)-1];

}

Решение

Заполним треугольную матрицу ответами для всех возможных значений $m$ и $n$ . Логика заполнения такая — если поле выглядит как полоска клеток, черепахе идти можно будет только вправо. Значит в первой строке (как и в столбце) будут все элементы равные 1. Поскольку в каждой клетке есть два варианта движения (вправо или вверх), остальные элементы будут заполняться как сумма ранее найденных значений для клеток справа текущей и над ней. Для диагональных элементов оба соседних расположены симметрично (то есть они равны), поэтому диагональный элемент будет равен удвоенному соседу справа. Решение намного быстрее, если нужно пройти много тестов, но тратит память на запоминание всех ответов.

Ссылки (циклы)

Ссылки (динамическое программирование)

Related Images:

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$. На каждом шаге если нам разрешено сделать столько суперпрыжком сколько мы сделали обновляем общее минимальное количество затраченной энергии если оно больше чем результат, полученный нами на последней платформе. Таким образом на каждом шаге мы будем получать минимальные затраты для определенного количества прыжков. Таким образом минимальное из этих самых ответов и будет тем что требуется в задаче.

Оптимизация

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

Ссылки

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 8651. Браслети (Bangles)

20/03/2019 by Владислав Бебик

Задача

Шпигунам-конкурентам вдалося потрапити на склад запасних частин фірми «Magic & Stupidity», яка виготовляла магічні браслети. Стало зрозуміло, що всі браслети складалися з чотирьох різних деталей, кожна з яких мала на кінцях замки різних типів (розрізнялися за номерами). Вони з’єднувалися по колу, причому у сусідніх частин замки повинні мати однаковий номер. Знайшлося $N$ різних типів замків (позначимо їх номерами від $1$ до $N$) і $М$ типів деталей, які визначаються парою номерів замків (порядок несуттєвий). Напишіть програму, яка б підраховувала скільки існує різних наборів з чотирьох деталей для виготовлення браслетів фірмою «Magic & Stupidity».

Вхідні дані

Програма читає з першого рядка числа $N$ (кількість типів замків) та $M$ (кількість типів деталей). $(4 ≤ N ≤ 300)$. У $M$ наступних рядках наведені параметри деталей (пара номерів замків). Всі пари різні.

Вихідні дані

Програма визначає кількість варіантів браслетів.

Объяснение:

Існує два варіанти з’єднання: $(3,4) – (4,2) – (2,5) – (5,3)$ та $(1,4) – (4,5) – (5,3) – (3,1)$ У сусідніх деталях існують однакові замки. Це також справедливо для першої та останньої(четвертої) деталі.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	5 7 1 3 1 4 2 4 2 5 3 4 3 5 4 5	2
2	5 8 1 3 1 4 2 3 2 4 2 5 3 4 3 5 4 5	5

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

#include <iostream>
#define MAX 301
using namespace std;

int x[MAX][MAX];
int y[MAX][MAX];
int main() {
    int n,m,i,j,e,u,v,q,z,r=0;
    scanf("%d%d",&n,&m);
    for (i=0; i<m; i++) {
        scanf("%d%d",&u,&v);
        x[u-1][v-1]=1; x[v-1][u-1]=1;
    }
    for (i=0; i<n-1; i++) {
        for (j=i+1; j<n; j++) {
            q=0;
            for (e=0; e<n; e++) {
                if (x[i][e]==1 && x[j][e]==1) q++;
            }
            y[i][j]=q;
        }
    }
    for (e=0; e<n; e++) {
        for (i=e+1; i<n; i++) {
            if (x[e][i]==1) {
                for (j=i+1; j<n; j++) {
                    if (x[e][j]==1) {
                        z=y[i][j];
                        if (z>1) {
                            z--;
                            r+=z;
                            y[i][j]=z;
                        }
                    }
                }
            }
        }
    }
    printf("%d",r);
    return 0;
}

#include <iostream>

#define MAX 301

using namespace std;

int x[MAX][MAX];

int y[MAX][MAX];

int main() {

int n,m,i,j,e,u,v,q,z,r=0;

scanf("%d%d",&n,&m);

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

scanf("%d%d",&u,&v);

x[u-1][v-1]=1; x[v-1][u-1]=1;

}

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

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

q=0;

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

if (x[i][e]==1 && x[j][e]==1) q++;

}

y[i][j]=q;

}

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

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

if (x[e][i]==1) {

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

if (x[e][j]==1) {

z=y[i][j];

if (z>1) {

z--;

r+=z;

y[i][j]=z;

}

printf("%d",r);

return 0;

}

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

В ячейке $x[u-1][v-1]$ стоит единица тогда и только тогда, когда у нас есть звено, имеющее на одном конце замок номер $u$, а на другом $- v$. Теперь построим таблицу, где будет записано в ячейке $y[u-1][v-1]$ количество их общих пар замков, где $u$ и $v$ это пара замков. Потом в первой таблице будем проходить по каждой строке и искать все возможные пары единиц в столбиках, пусть $u$ и $v$ это индекс выбранных столбиков. И если ячейка $y[u-1][v-1]$ больше единицы, то будем отнимать единицу в этой ячейке, чтобы отбросить случай, когда в браслете первый и четвёртый замок одинаковой. Полученное число в этой ячейке будем добавлять к ответу. А запоминать в эту же ячейку на единицу меньше, чтобы потом при подсчёте результата не посчитать один и тот же браслет два раза. Рассмотрим для наглядности пример: когда дано $5$ типов замков и $7$ типов деталей: $1-3, 1-4, 2-4, 2-5, 3-4, 3-5, 4-5$. То есть для каждой пары запомним количество общих замков, так как нам нужно, чтобы количество общих замков для пар было больше единицы, выпишем для наглядности нужные: $1-5$ имеет $2$, $2-3$ имеет $2$, $3-4$ имеет $2$, $4-5$ имеет $2$ общих замка. В первой строке в первой таблице единственная пара это $3-4$, так как общих замков этой пары больше единицы, то пара нам подходит. То есть варианты браслета $1-3-4-1$ и $1-3-4-5$, поэтому отнимем единицу и получим количество нужных браслетов, то есть один браслет уже есть, это $1-3-4-5$. Смотрим дальше, во второй строке тоже одна пара $4-5$. Варианты получаемый браслетов $2-4-5-2$ и $2-4-5-3$, опять отнимем один вариант и остальные браслеты запомним, то есть браслет $2-4-5-3$. В третей строке получится пара $4-5$, но там один вариант $3-4-5-3$, что не подходит, если бы мы ранее не запоминали на единицу меньше, то сейчас мы бы посчитали второй раз тот же браслет $3-4-5-2$, который уже есть. В итоге мы получили $2$ браслета, то есть $1-3-4-5$ и $2-4-5-3$, что есть верным ответом.

Ссылки

Related Images:

e-olymp 15. Мышка и зернышки

17/06/2017 by Валентина Андриеш

Условие задачи:

В индийском храме пол прямоугольной формы выложен одинаковыми квадратными плитками 1 х 1, на каждую из которых высыпано от 0 до k зернышек (k ≤ 30000). Размеры пола m х n. Мышка выбегает из левого нижнего угла пола храма и двигается к входу в другую норку, расположенную в противоположном углу. Мышка может двигаться только вправо или вперед, собирая все зернышки с плитки, на которой она находится.

Найти маршрут, двигаясь по которому мышка соберет наибольшее количество зернышек.

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

Первая строка содержит числа m и n – размеры пола (1 ≤ m, n ≤ 100). Далее идет m строк, начиная сверху, в каждой из которых размещено n чисел – количество зернышек на соответствующей плитке.

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

Вывести маршрут движения мышки в формате: RRFFFRF (F – шаг вперед, R – шаг вправо).

Тесты:

Входные данные	Выходные данные
2 3 3 2 4 1 5 1	RFR
4 4 34 5 7 8 7 8 9 23 1 2 909 54 3 4 8 0	RRFRFF
7 8 23 4 7 8 94 23 5 6 2 9 7 56 83 5 44 2 1 2 3 4 5 6 7 8 8 7 6 5 4 32 2 1 90 87 3 5 4 3 2 5 28 75 60 94 33 3 2 7 76 92000 402 28 3 2 11 200	RFRRFFFFRFRRR

Код на С++:

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main() {
    int m,n;
    long long X[100][100];
    string ans;
    cin>>n>>m;
    for (int i=n-1; i>=0; i--){
        for (int j=0; j<m; j++)cin>>X[i][j];
    }
    for(int i=1;i<n;i++)X[i][0]=X[i][0]+X[i-1][0];
    for(int j=1;j<m;j++)X[0][j]=X[0][j]+X[0][j-1];
    for (int i=1; i<n; i++){
        for (int j=1; j<m; j++) X[i][j]=X[i][j]+max(X[i - 1][j], X[i][j - 1]);
    }
    int k=n-1, t=m-1;
    while (k>0 || t>0){
        if (k>0 && t>0){
            if (X[k-1][t]>X[k][t-1]){
                ans+="F";
                k--;
            }
            else{
                ans+="R";
                t--;    
            } 
        }
        else if (k==0){
            ans+="R";
            t--;
        }
        else if (t==0){
            ans+="F";
            k--;
        }
    }
    reverse(ans.begin(),ans.end());
    cout<<ans;
    return 0;
}

#include <iostream>

#include <algorithm>

#include <string>

using namespace std;

int main() {

int m,n;

long long X[100][100];

string ans;

cin>>n>>m;

for (int i=n-1; i>=0; i--){

for (int j=0; j<m; j++)cin>>X[i][j];

}

for(int i=1;i<n;i++)X[i][0]=X[i][0]+X[i-1][0];

for(int j=1;j<m;j++)X[0][j]=X[0][j]+X[0][j-1];

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

for (int j=1; j<m; j++) X[i][j]=X[i][j]+max(X[i - 1][j], X[i][j - 1]);

}

int k=n-1, t=m-1;

while (k>0 || t>0){

if (k>0 && t>0){

if (X[k-1][t]>X[k][t-1]){

ans+="F";

k--;

}

else{

ans+="R";

t--;

}

else if (k==0){

ans+="R";

t--;

}

else if (t==0){

ans+="F";

k--;

}

reverse(ans.begin(),ans.end());

cout<<ans;

return 0;

}

Код на Java:

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

class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        int n=in.nextInt();
        int m=in.nextInt();
        long[][] X = new long[100][100];
        String ans = new String("");
        for (int i=n-1; i>=0; i--){
            for (int j=0; j<m; j++)X[i][j]=in.nextLong();
        }
        for(int i=1;i<n;i++)X[i][0]=X[i][0]+X[i-1][0];
        for(int j=1;j<m;j++)X[0][j]=X[0][j]+X[0][j-1];
        for (int i=1; i<n; i++){
            for (int j=1; j<m; j++) X[i][j]=X[i][j]+Math.max(X[i - 1][j], X[i][j - 1]);
        }
        int k=n-1, t=m-1;
        while (k>0 || t>0){
            if (k>0 && t>0){
                        if (X[k-1][t]>X[k][t-1]){
                            ans+="F";
                            k--;
                        }
                        else{
                            ans+="R";
                            t--;    
                        }
            }
                    else if (k==0){
                        ans+="R";
                        t--;
            }
            else if (t==0){
                        ans+="F";
                        k--;
            }
        }
        String reverse = new StringBuffer(ans).reverse().toString();
        System.out.println(reverse);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

Scanner in = new Scanner(System.in);

int n=in.nextInt();

int m=in.nextInt();

long[][] X = new long[100][100];

String ans = new String("");

for (int i=n-1; i>=0; i--){

for (int j=0; j<m; j++)X[i][j]=in.nextLong();

}

for(int i=1;i<n;i++)X[i][0]=X[i][0]+X[i-1][0];

for(int j=1;j<m;j++)X[0][j]=X[0][j]+X[0][j-1];

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

for (int j=1; j<m; j++) X[i][j]=X[i][j]+Math.max(X[i - 1][j], X[i][j - 1]);

}

int k=n-1, t=m-1;

while (k>0 || t>0){

if (k>0 && t>0){

if (X[k-1][t]>X[k][t-1]){

ans+="F";

k--;

}

else{

ans+="R";

t--;

}

else if (k==0){

ans+="R";

t--;

}

else if (t==0){

ans+="F";

k--;

}

String reverse = new StringBuffer(ans).reverse().toString();

System.out.println(reverse);

}

Описание решения задачи:

Представим пол индийского храма в виде двумерного массива. Т.к по условию движение мышки начинается с левого нижнего угла, при заполнении произойдет сдвиг, где позиция с изначальным номером [latex][n-1][0][/latex] примет позицию под номером [latex][0][0][/latex] и так далее пока данный сдвиг не достигнет плитки с номером [latex][n-1][0][/latex], где станет клеткой [latex][n-1][m-1][/latex]. Далее с помощью обхода в несколько циклов пересчитаем ячейки массива [latex]X[/latex] так, чтобы [latex]X[i][j][/latex] содержало максимальное количество зернышек, которое можно собрать по достижении плитки [latex](i, j)[/latex]. Переместимся в конец массива, в позицию под номером [latex]X[n-1][m-1][/latex]. Двигаясь в начальную клетку по закону, что предыдущая клетка слева или снизу должна содержать максимальное количество зернышек из всех возможных путей мыши, записываем в строку соответствующую букву, которая указывает на сделанный ход. По достижению цели мы получаем строку почти с готовым ответом. Перевернем ее, и теперь она указывает правильный путь не с конца в начало, а с начала в конец, что и требовалось. Выведем ответ.

Код задачи на с++
Код задачи на Java
Засчитанное решение на C++
Засчитанное решение на Java

Related Images:

e-olymp 1281. Простая задачка Шарика

12/06/2017 by Иванна Ялымова

Задача
Ещё задолго до того, как Шарик нашёл умную книжку, утерянную Печкиным, когда он только начинал свои эксперименты по распиливанию шахматных досок, когда ещё на шахматной доске белые поля были белыми, а чёрные – чёрными, он задал одну из своих первых задачек Матроскину.

«Сколько разных последовательностей длины [latex]n[/latex] можно составить из клеток распиленных шахматных досок, если ни в одной из последовательностей никакие три белых поля не должны идти подряд»?

Матроскин так и не решил ещё эту задачку, так что ваша задача помочь ему.

Входные данные
Длина последовательности [latex]n[/latex] ([latex]n ≤ 64[/latex]).

Выходные данные
Вывести количество указанных последовательностей.

Тесты

Входные данные	Выходные данные
1	2
2	4
3	7

Код программы на С++

#include<iostream>  
using namespace std;
     
int main() {
    long n,x1,x2,x3,x4;
    cin >> n;
    x1=2;
    x2=4;
    x3=7;
    for (int i=3; i<n; i++) {
        x4=x1+x2+x3;
        x1=x2;
        x2=x3;
        x3=x4;    
    }
    if (n==1) 
        cout << 2 << endl; 
    else if (n==2) 
        cout << 4 << endl; 
    else if (n==3)
        cout << 7 << endl; 
    else 
        cout << x4 << endl; 
    return 0;
}

#include<iostream>

using namespace std;

int main() {

long n,x1,x2,x3,x4;

cin >> n;

x1=2;

x2=4;

x3=7;

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

x4=x1+x2+x3;

x1=x2;

x2=x3;

x3=x4;

}

if (n==1)

cout << 2 << endl;

else if (n==2)

cout << 4 << endl;

else if (n==3)

cout << 7 << endl;

else

cout << x4 << endl;

return 0;

}

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

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

class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        long x1,x2,x3;
        long x4=0;
        long n=in.nextLong();
        x1=2;
        x2=4;
        x3=7;
        for (int i=3; i<n; i++) {
            x4=x1+x2+x3;
            x1=x2;
            x2=x3;
            x3=x4;    
        }
        if (n==1) 
            System.out.println(2); 
        else if (n==2) 
            System.out.println(4); 
        else if (n==3)
            System.out.println(7); 
        else 
            System.out.println(x4);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

Scanner in = new Scanner(System.in);

long x1,x2,x3;

long x4=0;

long n=in.nextLong();

x1=2;

x2=4;

x3=7;

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

x4=x1+x2+x3;

x1=x2;

x2=x3;

x3=x4;

}

if (n==1)

System.out.println(2);

else if (n==2)

System.out.println(4);

else if (n==3)

System.out.println(7);

else

System.out.println(x4);

}

Решение
Для решения задачи воспользуемся рекуррентным соотношением [latex]f \left( n \right) = f \left( n-1 \right)+f \left( n-2 \right)+f \left( n-3 \right)[/latex], где [latex]f[/latex] — функция, возвращающая ответ на поставленную задачу. Из условия следует, что для любой последовательности рассматривать следует только три варианта её последних элементов: …Ч, …ЧБ, …ЧББ (где Ч — чёрная клетка, Б — белая), так как в случае, если конец последовательности квадратов содержит только чёрный квадрат, чёрный и белый или чёрный и два белых, то нарушить последовательность могли только предшествующие этим окончаниям, которые имеют длины 1, 2, и 3 соответственно, последовательности. Именно это и влечёт справедливость указанного выше рекуррентного соотношения. Значения [latex]f \left( n \right)[/latex] при [latex]n \le 3[/latex] можно вычислить вручную и сохранить, а остальные вычислять в цикле с использованием предыдущих, вплоть до получения требуемого.

Ссылки
Код на ideone.com (C++)
Код на ideone.com (Java)
Задача с сайта e-olymp.com.
Засчитанное решение.

Related Images:

e-olymp 5062. Максимальный подпалиндром

10/06/2017 by Тимур Фирсов

Задача

Из данной строки удалите наименьшее количество символов так, чтобы получился палиндром (строка, одинаково читающаяся как справа налево, так и слева направо).

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

Непустая строка длиной не более [latex]100[/latex] символов. Строка состоит только из заглавных латинских букв.

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

Вывести строку-палиндром максимальной длины, которую можно получить из исходной вычёркиванием нескольких букв. При наличии нескольких решений необходимо вывести одно (любое) из них.

Тесты

№	Входные данные	Выходные данные
1	QWEERTYY	YY
2	QWEERT	EE
3	BAOBAB	BAOAB
4	ABCDCBA	ABCDCBA

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

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string **dp;
int main() {
    string s1,s2;
    long long i,j;
    cin>>s1;
    s2=s1;
    long long m=s1.size()+1;
    reverse(s2.begin(),s2.end());
    dp=new string* [m];
    for(i=0;i<m;i++)dp[i]=new string [m];
    for(i=1;i<m;i++){
        for(j=1;j<m;j++){
            if(s1[i-1]==s2[j-1])dp[i][j]=dp[i-1][j-1]+s2[j-1];
            else{
                if(dp[i-1][j].size()>dp[i][j-1].size())dp[i][j]=dp[i-1][j];
                else dp[i][j]=dp[i][j-1];
            }
        }
    }
    cout<<dp[m-1][m-1];
    return 0;
}

#include <iostream>

#include <string>

#include <algorithm>

using namespace std;

string **dp;

int main() {

string s1,s2;

long long i,j;

cin>>s1;

s2=s1;

long long m=s1.size()+1;

reverse(s2.begin(),s2.end());

dp=new string* [m];

for(i=0;i<m;i++)dp[i]=new string [m];

for(i=1;i<m;i++){

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

if(s1[i-1]==s2[j-1])dp[i][j]=dp[i-1][j-1]+s2[j-1];

else{

if(dp[i-1][j].size()>dp[i][j-1].size())dp[i][j]=dp[i-1][j];

else dp[i][j]=dp[i][j-1];

}

cout<<dp[m-1][m-1];

return 0;

}

Засчитанное решение на e-olymp.

Решение

Так как палиндром читается одинаково как справа налево, так и слева направо, то максимальным подпалиндромом будет наибольшая общая подстрока двух строк: исходной строки [latex]s_1[/latex] и этой же строки, но записанной в обратном порядке [latex]s_2[/latex] (как, если бы мы её читали справа налево). Для нахождения их наибольшей общей подстроки следует заполнить таблицу [latex]D[/latex] размером [latex] (n+1)\times(n+1) [/latex], где [latex]n[/latex]-длина строки. Заполнять таблицу будем методом аналогичным поиску длины наибольшей общей подстроки, но в каждой ячейке [latex]D_{i j}[/latex] таблицы будем хранить наибольшую подстроку строки, содержащей только первые [latex]i[/latex] символов [latex]s_1[/latex], и строки, содержащей только [latex]j[/latex] первых символов [latex]s_2[/latex]. В ячейках [latex]D_{0 j}[/latex] и [latex]D_{i 0}[/latex] будем хранить пустые строки. Если [latex]i[/latex]-й символ строки [latex]s_1[/latex] равен [latex]j[/latex]-ому символу строки [latex]s_2[/latex], то в ячейку [latex]D_{i j}[/latex] запишем конкатенацию строки из ячейки [latex]D_{i-1 j-1}[/latex] и данного символа. Иначе в ячейке [latex]D_{i j}[/latex] будем хранить наибольшую из строк [latex]D_{i-1 j}[/latex] и [latex]D_{i j-1}[/latex]. Таким образом в ячейке [latex]D_{n n}[/latex] будет хранится наибольший подпалиндром исходной строки.

Ссылки

Related Images:

e-olymp 1285. Деление Гольдбаха

10/06/2017 by Тимур Фирсов

Задача

Широко известна проблема Гольдбаха! Вот одна из её версий:

Любое нечетное число больше [latex]17[/latex] можно записать в виде суммы трёх нечётных простых чисел;
Любое чётное число больше [latex]6[/latex] можно записать в виде суммы двух нечётных простых чисел.

Если число чётное, то мы раскладываем его на суммы двух простых разных нечётных, а если нечётное — то на суммы трёх простых разных нечётных. Такой способ разложения для заданного [latex]N[/latex] назовём делением Гольдбаха и обозначим как [latex]G\left( N \right)[/latex].
Зная заданное число [latex]N[/latex], найти [latex]\left| G\left( N \right) \right| [/latex], т.е. количество различных [latex]G(N)[/latex].

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

Входные данные содержат несколько тестовых случаев.
Каждый тест в отдельной строке содержит одно единственное число [latex]N \left( 1\le N\le 20000 \right) [/latex].
Ввод продолжается до конца входного файла.

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

Для каждого тестового случая вывести в отдельной строке одно число — найденное значение [latex]\left| G\left( N \right) \right| [/latex].

Тесты

№	Входные данные	Выходные данные
1	5 8 18 19 20	0 1 2 1 2
2	13 22 78 4 150	0 2 7 0 12
3	2000	37
4	6 8 17 19 337	0 1 0 1 195

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

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

bool prime (int x){ //функция для проверки простоты нечётного числа
    bool pr=true;
    for(int i=2; i<=sqrt(x);i++)if(!(x%i))pr=false;
    return pr;
}
int main() {
    vector <int> v,prime_v;
    unordered_map <int,bool> prime_m;
    int u,i,j,maxx=0;
    while(cin>>u){
        v.push_back(u);
        maxx=max(maxx,u);//максимальное значение во входном потоке
    }
    for(i=3;i<=maxx;i+=2){
        if(prime(i)){
            prime_m[i]=true;
            prime_v.push_back(i); 
        }
    }
    int *dp,k;
    dp = new int [maxx+1];
    for(i=0;i<=maxx;i++)dp[i]=0;
    for(i=8;i<=maxx;i++){//заполняем массив значениями |G(i)|
        if(i%2){
            for(j=0;(j<prime_v.size())&&(prime_v[j]<i);j++){
                k=i-prime_v[j];
                if(dp[k]){
                    dp[i]+=dp[k];
                    if((prime_m[k-prime_v[j]])&&((k-prime_v[j])!=prime_v[j]))--dp[i];
                }
            }
        }
        else{
            for(j=0;(j<prime_v.size())&&(prime_v[j]<(i/2));j++){
                k=i-prime_v[j];
                if(prime_m[k])dp[i]++;
            }
        }
        if(i%2)dp[i]/=3;
    }
    for(i=0;i<v.size();i++)cout<<dp[v[i]]<<'\n';
    return 0;
}

#include <iostream>

#include <vector>

#include <unordered_map>

#include <cmath>

using namespace std;

bool prime (int x){ //функция для проверки простоты нечётного числа

bool pr=true;

for(int i=2; i<=sqrt(x);i++)if(!(x%i))pr=false;

return pr;

}

int main() {

vector <int> v,prime_v;

unordered_map <int,bool> prime_m;

int u,i,j,maxx=0;

while(cin>>u){

v.push_back(u);

maxx=max(maxx,u);//максимальное значение во входном потоке

}

for(i=3;i<=maxx;i+=2){

if(prime(i)){

prime_m[i]=true;

prime_v.push_back(i);

}

int *dp,k;

dp = new int [maxx+1];

for(i=0;i<=maxx;i++)dp[i]=0;

for(i=8;i<=maxx;i++){//заполняем массив значениями |G(i)|

if(i%2){

for(j=0;(j<prime_v.size())&&(prime_v[j]<i);j++){

k=i-prime_v[j];

if(dp[k]){

dp[i]+=dp[k];

if((prime_m[k-prime_v[j]])&&((k-prime_v[j])!=prime_v[j]))--dp[i];

}

else{

for(j=0;(j<prime_v.size())&&(prime_v[j]<(i/2));j++){

k=i-prime_v[j];

if(prime_m[k])dp[i]++;

}

if(i%2)dp[i]/=3;

}

for(i=0;i<v.size();i++)cout<<dp[v[i]]<<'\n';

return 0;

}

Засчитанное решение на e-olymp.com

Решение

Поместим все тестовые случаи в вектор и найдём максимальное из данных чисел — [latex]max[/latex]. Затем найдём все нечётные простые числа меньшие [latex]max[/latex] (единственное чётное простое число — [latex]2[/latex]). Заведём массив размером [latex]max+1[/latex], [latex]i[/latex]-м элементом которого будет [latex]\left| G\left( i \right) \right| [/latex]. Тогда, если [latex]i[/latex]- чётное, то одно из слагаемых суммы [latex]a_{i}+b_{i}[/latex] двух простых разных нечётных чисел будем подбирать из найденных ранее простых нечётных чисел, но строго меньших [latex]\frac { i }{ 2 } [/latex], чтобы разбиения, отличающиеся только порядком следования частей считать равными, и выполнялось неравенство [latex]a_{i}\neq b_{i}[/latex]. Если разность [latex]i[/latex] и подобранного таким образом числа — нечётное простое число, то это деление Гольдбаха, тогда увеличиваем на единицу [latex]\left| G\left( i \right) \right| [/latex]. Если [latex]i[/latex] — нечётное, то [latex]a_{i}[/latex]из суммы [latex]a_{i}+b_{i}+c_{i}[/latex] трёх простых разных нечётных чисел будем подбирать из всех простых нечётных чисел строго меньших [latex]i[/latex]. Разностью [latex]i[/latex] и подобранного числа [latex]a_{i}[/latex] (разность двух нечётных) будет чётное число [latex]j[/latex], [latex]\left| G\left( j \right) \right| [/latex] мы уже нашли ранее. Тогда можем представить [latex]\left| G\left( j \right) \right| [/latex] различных разложений [latex]G\left( i \right)[/latex] в виде [latex]a_{i}+G\left( j \right)_{k}[/latex] или [latex]a_{i}+{a_j}_{k}+{b_j}_{k}[/latex], где [latex]k=\overline { 1,\left| G\left( j \right) \right| } [/latex], a [latex]G\left( j \right)_{k}[/latex] — [latex]k[/latex]-е разбиение числа [latex]j[/latex]. Значит все полученные [latex]\left| G\left( j \right) \right| [/latex] будем прибавлять к [latex]\left| G\left( i \right) \right| [/latex], а чтоб избежать ситуаций [latex]a_i={a_j}_k[/latex] и [latex]a_i={b_j}_k[/latex], если [latex]i-2a_{i}[/latex] — простое число не равное [latex]a_{i}[/latex] (то есть при некотором значении [latex]k[/latex] одно из чисел [latex] G\left( j \right)_{k} [/latex] равно [latex]a_{i}[/latex] и не равно второму числу, так как [latex]{a_{j}}_k\neq {b_{j}}_k[/latex] мы учли ранее), то будем отнимать единицу от [latex]\left| G\left( i \right) \right| [/latex]. В разбиениях [latex]j[/latex] мы не учитываем порядок следования частей. Чтобы не учитывать его в и разбиениях числа [latex]i[/latex], разделим полученный результат [latex]\left| G\left( i \right) \right| [/latex] на [latex]3[/latex].

Ссылки

Related Images:

e-olymp 7447. Обрезка строки

12/05/2017 by Эммануил Прокопов

Задача с сайта e-olymp.com.

Условие задачи

Имеется строка [latex]s[/latex]. Разрешается взять два любых одинаковых соседних символа и удалить их из строки. Эту операцию можно производить пока имеется возможность. Сначала Вы можете выбрать любое количество символов в строке и удалить их. Определить наименьшее количество символов, которое Вы можете удалить сначала так, чтобы затем выполняя разрешенную операцию, получить пустую строку.

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

Содержит строку [latex]s[/latex] ([latex]1 ≤[/latex] длина[latex]\left( s \right) [/latex] [latex]≤ 100)[/latex].

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

Вывести наименьшее количество символов, которое следует удалить сначала.

Тесты

№	Входные данные	Выходные данные
1	abbcddka	2
2	ABBA	0
3	abcde	5
4	abbac	1

Код на C++

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

int **answers;
string s;

int calculate(int l, int r){
    if(l > r) return 0;  //Если индекс левой границы отрезка больше индекса правой.
    if(answers[l][r] == -1){ //Если ответ для данного отрезка ещё не известен, находим его.
        answers[l][r] = s.size();
        if(s[l] == s[r]) answers[l][r] = min(answers[l][r], calculate(l+1, r-1));
        for(int i = l; i < r; ++i){
            answers[l][r] = min(answers[l][r], calculate(l, i) + calculate(i+1, r));
        }
    }
    return answers[l][r];
}

int main() {
    getline(cin, s); //Ввод строки.
    
    answers = new int*[s.size()];
    for(int i = 0; i < s.size(); ++i){
        answers[i] = new int[s.size()];
    }
    //Заполнение массива начальными значениями.
    for(int i = 0; i < s.size(); ++i){
        for(int j = 0; j <= s.size(); ++j){
            if(i == j) answers[i][j] = 1;
            else answers[i][j] = -1;
        }
    }
    //Вывод ответа.
    cout<<calculate(0, s.size()-1);
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

int **answers;

string s;

int calculate(int l, int r){

if(l > r) return 0; //Если индекс левой границы отрезка больше индекса правой.

if(answers[l][r] == -1){ //Если ответ для данного отрезка ещё не известен, находим его.

answers[l][r] = s.size();

if(s[l] == s[r]) answers[l][r] = min(answers[l][r], calculate(l+1, r-1));

for(int i = l; i < r; ++i){

answers[l][r] = min(answers[l][r], calculate(l, i) + calculate(i+1, r));

}

return answers[l][r];

}

int main() {

getline(cin, s); //Ввод строки.

answers = new int*[s.size()];

for(int i = 0; i < s.size(); ++i){

answers[i] = new int[s.size()];

}

//Заполнение массива начальными значениями.

for(int i = 0; i < s.size(); ++i){

for(int j = 0; j <= s.size(); ++j){

if(i == j) answers[i][j] = 1;

else answers[i][j] = -1;

}

//Вывод ответа.

cout<<calculate(0, s.size()-1);

return 0;

}

Код на Java

import java.util.*;

class Main
{
    static int[][] answers;
    static String s;

    static int calculate(int l, int r){
        if(l > r) return 0;  //Если индекс левой границы отрезка больше индекса правой.
        if(answers[l][r] == -1){ //Если ответ для данного отрезка ещё не известен, находим его.
            answers[l][r] = s.length();
            if(s.charAt(l) == s.charAt(r)) answers[l][r] = Math.min(answers[l][r], calculate(l+1, r-1));
            for(int i = l; i < r; ++i){
                answers[l][r] = Math.min(answers[l][r], calculate(l, i) + calculate(i+1, r));
            }
        }
        return answers[l][r];
    }

    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        s = in.nextLine();  //Ввод строки.
        
        answers = new int[s.length()][s.length()];
        //Заполнение массива начальными значениями.
        for(int i = 0; i < s.length(); ++i){
            for(int j = 0; j < s.length(); ++j){
                if(i == j) answers[i][j] = 1;
                else answers[i][j] = -1;
            }
        }
        //Вывод ответа.
        System.out.print(calculate(0, s.length()-1));
    }
}

import java.util.*;

class Main

{

static int[][] answers;

static String s;

static int calculate(int l, int r){

if(l > r) return 0; //Если индекс левой границы отрезка больше индекса правой.

if(answers[l][r] == -1){ //Если ответ для данного отрезка ещё не известен, находим его.

answers[l][r] = s.length();

if(s.charAt(l) == s.charAt(r)) answers[l][r] = Math.min(answers[l][r], calculate(l+1, r-1));

for(int i = l; i < r; ++i){

answers[l][r] = Math.min(answers[l][r], calculate(l, i) + calculate(i+1, r));

}

return answers[l][r];

}

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

{

Scanner in = new Scanner(System.in);

s = in.nextLine(); //Ввод строки.

answers = new int[s.length()][s.length()];

//Заполнение массива начальными значениями.

for(int i = 0; i < s.length(); ++i){

for(int j = 0; j < s.length(); ++j){

if(i == j) answers[i][j] = 1;

else answers[i][j] = -1;

}

//Вывод ответа.

System.out.print(calculate(0, s.length()-1));

}

Описание

Идея решения состоит в том, чтобы разбить строку на меньшие по длине подстроки и найти ответ на задачу для каждой из них. Для хранения строки используется переменная s, а ответы на подзадачи содержатся в двумерном массиве целых чисел answers. В answers[i][j] находится ответ для подстроки с i-ого по j-й символ включительно. В функции main сначала вводится строка s. Далее ширина и глубина массива answers устанавливаются равными длине s. После этого он заполняется начальными значениями. Значение [latex]-1[/latex] означает, что ответ для этой ячейки ещё не был найден. Однако очевидно, что если строка состоит ровно из одного символа, согласно условию задачи, его придётся удалить, значит, главную диагональ можно сразу заполнить единицами. Затем происходит вызов рекурсивной функции calculate, принимающей индексы левой и правой границ целевой подстроки. Первый раз она вызывается для всей строки от первого до последнего символа. Работает эта функция следующим образом: если индекс левой границы отрезка больше индекса правой, что, в случае данной задачи, не имеет смысла, она возвращает ноль. Иначе она возвращает ответ на задачу для данной подстроки, а если этого не делалось ранее, то предварительно находит его. Происходит это так: сначала значение ответа устанавливается равным длине подстроки, поскольку в худшем случае необходимо будет удалить её всю целиком. Если символы на концах подстроки одинаковые, они, как сказано в условии, будут удалены в дальнейшем, потому нужно рассматривать минимум из текущего значения ответа и ответа для подстроки без крайних символов. Однако может оказаться, что выгоднее удалить символы из каких-то двух меньших подстрок, потому далее в цикле рассматриваются все возможные комбинации двух подстрок, из которых можно составить конкатенацией текущую. В итоге получаем ответ на задачу для данной подстроки.

Код на ideone.com. (C++)
Код на ideone.com. (Java)
Засчитанное решение на e-olymp.