Category Archives: 6. Многомерные массивы

Работа с прямоугольными массивами.

Массивы

Опубликовано: 20/10/2014

К этой рубрике относятся задания на использование классических массивов, работе с ними через указатели и ссылочные типы. Желательно снова перечитать параграф 3.5 и 3.6 из праймера. Размер массива обычно будет читаться из входного потока. Это вынуждает использовать динамические массивы. В качестве заготовки можно использовать такой код:

#include <iostream>
using namespace std;
 
int main() {
    size_t n;   
    cin >> n;
    double *x = new double [n];
    for(size_t i = 0; i < n; i++)
        cin >> x[i];
        
    // Processing 
    for(size_t i = 0; i < n; i++)
        cout << "x[" << i << "] = " << x[i] << "\t";
}

#include <iostream>

using namespace std;

int main() {

size_t n;

cin >> n;

double *x = new double [n];

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

cin >> x[i];

// Processing

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

cout << "x[" << i << "] = " << x[i] << "\t";

}

Выполнить программу Обратите внимание, что цикл в котором … Continue reading →

нет комментариев

В классе и дома решаются следующие тренировочные задачи (1 балл):

Шоколад

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

e-olymp 396. Дождь

24/11/2021 by Александр Мармалюк

Условие

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

Напишите программу, которая по координате $\ x_0\ $ точки появления капли над землей вычисляет координату $x$ точки соприкосновения капли с землей $\ \left(y = 0\right).\ $ Будем рассматривать двумерный вариант (на плоскости) этой задачи. Пусть препятствия – это наклонные непересекающиеся отрезки, а капля имеет точечные размеры. Капля падает вертикально вниз из точки, расположенной выше любого из препятствий. Если капля при падении соприкасается с отрезком-препятствием, то она стекает по отрезку вниз, пока не упадет вертикально вниз с меньшего по высоте конца отрезка.

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

Во входном файле в первой строке содержатся два целых числа через пробел – координата $\ x_0\ $ точки появления капли $\ \left( 0 \lt x_0 \lt 10000\right)\ $ и количество отрезков-препятствий $\ N\ (0 \leqslant N \leqslant 100).\ $ Далее следует $\ N\ $ строк, каждая из которых содержит четыре разделенные пробелами числа $\ x_1,\ $ $\ y_1,\ $ $\ x_2,\ $ $\ y_2\ $ – координаты левого и правого концов отрезка-препятствия (все числа целые и находятся в диапазоне от $\ 0$\ до $\ 10000\ $, $\ x_1 \lt x_2,$ $y_1 \neq y_2.\ $ Отрезки не пересекаются и не соприкасаются.

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

В выходной файл вывести одно целое число – координату $\ x\ $ точки соприкосновения капли с землей.

Тесты

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

30 4 25 35 40 30 1 32 20 30 33 22 50 29 18 10 33 19	18
7 5 1 6 10 8 5 3 8 2 6 10 11 9 9 10 14 12 6 6 12 7	8
4 4 1 1 3 3 2 3 0 6 7 3 5 2 6 5 9 6	4
8 3 8 6 2 4 7 4 9 3 6 1 10 2	2
2 3 5 9998 0 10000 7 9996 11 9994 4 9996 9 9993	9

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

#include <iostream>
#include <cmath>
#include <vector>
#define MAX_Y 10000;
using namespace std;
struct slide {
    double x1;
    double y1;
    double x2;
    double y2;
};
//высота соприкосновения капли с крышей [ур-ние прямой по 2-м точкам]
double f (slide x, double x0) {
    double dx = x.x2 - x.x1;
    double dy = x.y2 - x.y1;
    return ((dy*(x0 - x.x1))/dx + x.y1);
}
vector <slide> roof; //вектор всех крыш
//считывание и заполнение данных
void read (int n) {
    while (n--) {
        double a, b, c, d;
        slide x;
        cin >> a >> b >> c >> d;
        if (a < c) {
            x.x1 = a;
            x.y1 = b;
            x.x2 = c;
            x.y2 = d;
        }
        else
        {
            x.x1 = c;
            x.y1 = d;
            x.x2 = a;
            x.y2 = b;
        }
        roof.push_back(x);
    }
}
int main() {
    int n, x, y = MAX_Y + 1;
    slide a;
    cin >> x >> n;
    if (n == 0) {
        cout << x;
        return 0;
    }
    read (n);
    while (roof.size()) {
        int index = -1;
        int value = -1; //предполагаемая высока соприкосновения капли со следующей крышей
        bool no_projection = true;
        for (int i = 0; i < roof.size(); i++) { //поиск самой высокой крыши в точке х
            if ((x <= roof[i].x2) and (x >= roof[i].x1)) { //капля проектируется на и-тую крышу?
                no_projection = false;
                if ((f(roof[i], x) > value) and (f(roof[i], x) < y)) { //и-тая крыша выше ранее найденной?
                    value = f(roof[i], x);
                    index = i;
                }
            }
            if (min(roof[i].y1, roof[i].y2) > y) {  //крыша целиком осталась выше?
                roof.erase(roof.begin() + i);
                i--;
            }
        }
        if ((roof.size() == 0) or (no_projection)) {  //если удалили все крыши или свободно падает на землю
            cout << x;
            return 0;
        }
        if (roof[index].y1 < roof[index].y2)  //какой конец крыши ниже?
            x = roof[index].x1;
        else
            x = roof[index].x2;
        y = min(roof[index].y1, roof[index].y2); //сохранили новую ординату
        roof.erase(roof.begin() + index);
    }
    cout << x;
    return 0;
}

#include <iostream>

#include <cmath>

#include <vector>

#define MAX_Y 10000;

using namespace std;

struct slide {

double x1;

double y1;

double x2;

double y2;

};

//высота соприкосновения капли с крышей [ур-ние прямой по 2-м точкам]

double f (slide x, double x0) {

double dx = x.x2 - x.x1;

double dy = x.y2 - x.y1;

return ((dy*(x0 - x.x1))/dx + x.y1);

}

vector <slide> roof; //вектор всех крыш

//считывание и заполнение данных

void read (int n) {

while (n--) {

double a, b, c, d;

slide x;

cin >> a >> b >> c >> d;

if (a < c) {

x.x1 = a;

x.y1 = b;

x.x2 = c;

x.y2 = d;

}

else

{

x.x1 = c;

x.y1 = d;

x.x2 = a;

x.y2 = b;

}

roof.push_back(x);

}

int main() {

int n, x, y = MAX_Y + 1;

slide a;

cin >> x >> n;

if (n == 0) {

cout << x;

return 0;

}

read (n);

while (roof.size()) {

int index = -1;

int value = -1; //предполагаемая высока соприкосновения капли со следующей крышей

bool no_projection = true;

for (int i = 0; i < roof.size(); i++) { //поиск самой высокой крыши в точке х

if ((x <= roof[i].x2) and (x >= roof[i].x1)) { //капля проектируется на и-тую крышу?

no_projection = false;

if ((f(roof[i], x) > value) and (f(roof[i], x) < y)) { //и-тая крыша выше ранее найденной?

value = f(roof[i], x);

index = i;

}

if (min(roof[i].y1, roof[i].y2) > y) { //крыша целиком осталась выше?

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

i--;

}

if ((roof.size() == 0) or (no_projection)) { //если удалили все крыши или свободно падает на землю

cout << x;

return 0;

}

if (roof[index].y1 < roof[index].y2) //какой конец крыши ниже?

x = roof[index].x1;

else

x = roof[index].x2;

y = min(roof[index].y1, roof[index].y2); //сохранили новую ординату

roof.erase(roof.begin() + index);

}

cout << x;

return 0;

}

Решение

Для удобства создадим структуру slide, которая будет описывать координаты концов отрезка-крыши. Также будем считать, что первый конец отрезка находится левее (для этого будем менять местами точки в случае необходимости).
Будем представлять каждую крышу как отрезок прямой на плоскости. Для этого применим уравнение прямой по двум точкам, принадлежащим этой прямой:
$$\frac{x — x_1}{x_2 — x1}=\frac{y — y_1}{y_2 — y_1}$$
Чтобы проверить, может ли капля в текущий момент проектироваться на некоторую крышу, надо проверить, находится ли абсцисса капли между абсциссами концов отрезка-крыши, а также найти ту крышу, которая в абсциссе капли «выше всех» (другими словами, у какой из прямых, которым принадлежат те отрезки, на которые проектируется капля, наибольшее значение ординаты в абсциссе капли). Для этого создадим функцию, которая и будет возвращать искомое значение ординаты. Также важно убедиться в том, что эта крыша находится ниже текущего положения капли. Заметим, что если некоторая крыша целиком находится выше капли, то мы на неё уже никогда не попадем, поэтому её нужно удалить из вектора. Найдя нужную крышу, определим новые координаты капли после того, как она скатится по этой крыше. Если капля в свободном падении и на её пути больше нет препятствий (крыш не осталось или нет такой, на которую проектируется капля), то текущая абсцисса капли и будет ответом на задачу.

Ссылки

Условие задачи на eolymp.com
Решение задачи на ideone.com

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-olimp 9536. Сумма матриц

16/05/2020 by Елизавета Савицкая

Задача

Заданы две матрицы $A$ и $B$. Найдите их сумму $C$ = $A$ + $B$.

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

Первая строка содержит размеры матриц $n$ и $m$ $(1 \leqslant n, m \leqslant 100)$. Следующие $n$ строк содержат по $m$ целых чисел и описывают матрицу $A$. Далее следует пустая строка, после чего в таком же формате задается матрица $B$.

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

Выведите матрицу $С$: $n$ строк по $m$ целых чисел.

Тесты

Входные данные	Выходные данные
1 1 2 3	5
1 5 4 3 7 2 1 3 2 2 1 6	7 5 9 3 7
2 2 0 4 2 3 5 4 1 6	5 8 3 9
3 4 3 4 5 6 1 2 3 4 7 6 5 4 0 0 -3 -2 -1 3 4 5 5 6 1 2	3 4 2 4 0 5 7 9 12 12 6 6
3 3 2 -128 47 -365 5 56 243 42 12 678 43 76 4 345 -23 97 -453 18	680 -85 123 -361 350 33 340 -411 30

Код

#include <iostream>
using namespace std;

int main() {
   int n, m;
   cin >> n >> m;
   int matrix1[n][m];
   int matrix2[n][m];
   int matrix_sum[n][m] = {0};
   for(int i = 0; i < n; i++){
      for(int j = 0; j < m; j++){
         cin >> matrix1[i][j];
      }
   }
   for(int i = 0; i < n; i++){
      for(int j = 0; j < m; j++){
         cin >> matrix2[i][j];
      }
   }
   for(int i = 0; i < n; i++){
      for(int j = 0; j < m; j++){
         matrix_sum[i][j] = matrix1[i][j] + matrix2[i][j];
         cout << matrix_sum[i][j] << " ";
      }
      cout << endl;
   }
   return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, m;

cin >> n >> m;

int matrix1[n][m];

int matrix2[n][m];

int matrix_sum[n][m] = {0};

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

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

cin >> matrix1[i][j];

}

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

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

cin >> matrix2[i][j];

}

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

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

matrix_sum[i][j] = matrix1[i][j] + matrix2[i][j];

cout << matrix_sum[i][j] << " ";

}

cout << endl;

}

return 0;

}

Решение

Чтобы найти сумму двух матриц, необходимо сложить их соответствующие элементы.

Ссылки

Условие задачи на 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 9537. Транспонирование матрицы

21/12/2019 by Матвей Курочкин

Задача

Задана матрица [latex]A[/latex]. Транспонируйте ее.
Пусть [latex]B[/latex] — транспонированная матрица [latex]A[/latex]. Пусть [latex]B[/latex] — транспонированная матрица [latex]A[/latex]. Тогда [latex] B_{ij} = A_{ji}[/latex] [latex]\begin{pmatrix}
1&2 \\
3&4 \\
5&6
\end{pmatrix}^T = \begin{pmatrix}
1 &3 &5 \\
2 &4 &6
\end{pmatrix}[/latex]

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

Первая строка содержит размеры матрицы [latex]n[/latex] и [latex]m[/latex]. [latex]1 \leq m,n \leq 100 [/latex] Следующие [latex]n[/latex] строк содержат по [latex]m[/latex] целых чисел и описывают матрицу [latex]A[/latex].

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

Выведите транспонированную матрицу [latex]A[/latex]: [latex]m[/latex] строк по [latex]n[/latex] целых чисел.

Тесты

№	Входные данные	Выходные данные
1	3 2 1 2 3 4 5 6	1 3 5 2 4 6
2	3 3 0 1 2 1 0 3 2 3 0	0 1 2 1 0 3 2 3 0
3	4 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1	1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
4	10 3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30	1 4 7 10 13 16 19 22 25 28 2 5 8 11 14 17 20 23 26 29 3 6 9 12 15 18 21 24 27 30

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

Решение

При получении первой матрицы мы получаем индекс каждого элемента — [latex]i[/latex], [latex]j[/latex] и количество строк и столбцов — [latex]n[/latex] и [latex]m[/latex]. Зная саму матрицу, количество строк и столбцов мы можем создать матрицу, где строк столько, сколько столбцов в первой матрице, и наоборот.
Сама же перестановка элементов происходит посредством смены индекса строки и столбца — элемент [latex]a[/latex] с индексом [latex]i[/latex] строки и [latex]j[/latex] столбца становится элементом [latex]b[/latex] с индексом [latex]j[/latex] строки и [latex]i[/latex] столбца.

Cсылки

Условие на e-olymp
Код на ideone

Related Images:

e-olymp 841. Спираль

05/12/2019 by Валентин Цушко

Условие

Вывести квадрат, состоящий из $N \times N$ клеток, заполненных числами от $1$ до $N^{2}$ по спирали.

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

В первой строке находится единственное число $N (2 \leq N \leq 100)$.

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

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

Тесты

№	Входные данные	Выходные данные
1	3	1 2 3 8 9 4 7 6 5
2	4	1 2 3 4 12 13 14 5 11 16 15 6 10 9 8 7
3	5	1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9
4	10	1 2 3 4 5 6 7 8 9 10 36 37 38 39 40 41 42 43 44 11 35 64 65 66 67 68 69 70 45 12 34 63 84 85 86 87 88 71 46 13 33 62 83 96 97 98 89 72 47 14 32 61 82 95 100 99 90 73 48 15 31 60 81 94 93 92 91 74 49 16 30 59 80 79 78 77 76 75 50 17 29 58 57 56 55 54 53 52 51 18 28 27 26 25 24 23 22 21 20 19

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

#include <iostream>
using namespace std;
 
int main()
{
    int n, m = 1;
    cin >> n;
    int a[n][n];
    
    if(n % 2 != 0){
        a[(n / 2)][(n / 2)] = (n * n);      // если N - нечетное то находим центр матрицы и заполняем его числом N * N
    }
    
    for(int i = 0; i < (n / 2); i++){
        for(int j = i; j < (n - i); j++){   // (n - i) - чтоб с каждым разом сторона становилась меньше
            a[i][j] = m;
            m++;
        }
        for(int j = 1; j < (n - i - i); j++){   // начинаем с первого эл. так-как нулевой уже записан
            a[(j + i)][(n - i) - 1] = m;    // (n - i) - 1 - отнимаем 1 чтоб не выходило за рамки массива
            m++;
        }
        for(int j = (n - 2) - i; j >= i; j--){  // (n - 2) - i - отнимаем 1 чтоб не выходило за рамки массива и еще одну 1 
            a[(n - i) - 1][(j)] = m;            // потому-что предыдущий эл. уже заполнен.
            m++;
        }
        for(int j = ((n - i) - 2); j > i; j--){
            a[j][i] = m;
            m++;
        }
    }
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n - 1; j++){
            cout << a[i][j] << " " ;
        }
        cout << a[i][n - 1] << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

int n, m = 1;

cin >> n;

int a[n][n];

if(n % 2 != 0){

a[(n / 2)][(n / 2)] = (n * n); // если N - нечетное то находим центр матрицы и заполняем его числом N * N

}

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

for(int j = i; j < (n - i); j++){ // (n - i) - чтоб с каждым разом сторона становилась меньше

a[i][j] = m;

m++;

}

for(int j = 1; j < (n - i - i); j++){ // начинаем с первого эл. так-как нулевой уже записан

a[(j + i)][(n - i) - 1] = m; // (n - i) - 1 - отнимаем 1 чтоб не выходило за рамки массива

m++;

}

for(int j = (n - 2) - i; j >= i; j--){ // (n - 2) - i - отнимаем 1 чтоб не выходило за рамки массива и еще одну 1

a[(n - i) - 1][(j)] = m; // потому-что предыдущий эл. уже заполнен.

m++;

}

for(int j = ((n - i) - 2); j > i; j--){

a[j][i] = m;

m++;

}

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

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

cout << a[i][j] << " " ;

}

cout << a[i][n - 1] << endl;

}

return 0;

}

Решение

Для того чтобы решить эту задачу нам нужно определить способ заполнения. Первым делом, если $N$ — нечетное, то находим центр матрицы и заполняем его числом $N \times N $ a[(n / 2)][(n / 2)] = (n * n);. В условии написано, что “Не допускается начинать спираль в ином, кроме верхнего левого углу, закручивать спираль против часовой стрелки или изнутри наружу.”, то есть начинать мы будем с верхнего левого угла. Для этого мы сделаем цикл for(int i = 0; i < (n / 2); i++); , в котором сделаем 4 такта. Каждый такт заполняет определенную часть матрицы:

- 1 такт – заполняет верхнюю грань слева направо;
- 2 такт – заполняет правую грань сверху вниз;
- 3 такт – заполняет нижнюю грань справа налево;
- 4 такт – заполняет левую грань снизу вверх, как показано на рисунке ниже.

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

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

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 683. Частичная сумма матрицы

20/06/2019 by Дария Даниленко

Задача

Задана матрица чисел $a_{ij}$ где $1 \leqslant i \leqslant n$, $1 \leqslant j \leqslant m$. Для всех $i, j$ найдите $$S_{i,j}=\sum_{k=1, t=1}^{k\leqslant i, t \leqslant j}a_{kt}.$$

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

В первой строке записаны размеры матрицы — $n, m$ $(1 \leqslant n, m \leqslant 1000)$. В последующих $n$ строках записано по $m$ чисел $a_{ij}$ $(1 \leqslant a_{ij} \leqslant 1000)$.

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

Выведите $n$ строк по $m$ чисел $S_{i,j}$.

Тесты

Входные данные	Выходные данные
3 5 1 2 3 4 5 5 4 3 2 1 2 3 1 5 4	1 3 6 10 15 6 12 18 24 30 8 17 24 35 45
4 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1	1 2 3 4 2 4 6 8 3 6 9 12 4 8 12 16
6 7 15 78 69 36 567 654 5 54 54 52 81 237 5 98 987 2 65 5 32 89 67 541 89 4 32 4 1 40 68 7 345 6 21 23 56 9 5 7 2 5 4 1000	15 93 162 198 765 1419 1424 69 201 322 439 1243 1902 2005 1056 1190 1376 1498 2334 3082 3252 1597 1820 2010 2164 3004 3753 3963 1665 1895 2430 2590 3451 4223 4489 1674 1909 2451 2613 3479 4255 5521

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

#include <iostream>
using namespace std;

int x[1001][1001];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
          for (int j = 1; j <= m; j++) cin >> x[i][j];
    }
    for (int i = 1; i <= n; i++){
          for (int j = 1; j <= m; j++) x[i][j] += x[i-1][j] + x[i][j-1] - x[i-1][j-1];
    }
    for (int i = 1; i <= n; i++){
          for (int j = 1; j <= m; j++){
            cout << x[i][j]; 
            if (j != m) cout << " ";
          }
          cout << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int x[1001][1001];

int main() {

int n, m;

cin >> n >> m;

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

for (int j = 1; j <= m; j++) cin >> x[i][j];

}

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

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

}

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

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

cout << x[i][j];

if (j != m) cout << " ";

}

cout << endl;

}

return 0;

}

Решение

Создаем матрицу x[1001][1001] вне int main() . Сдвигаем индексацию массива на единицу и заполняем его. Таким образом первая строка и первый столбец у нас оказываются заполнены нулями. Чтобы не вычислять каждую новую $S_{i,j}$ от $(i+1)\cdot (j+1)$ предыдущих значений, воспользуемся основным свойством частичных сумм: если $$S_{i,j}=\sum_{k=1, t=1}^{k\leqslant i, t \leqslant j}a_{kt},$$ то тогда $S_{i,j} — a_{ij}=S_{i-1,j}+S_{i,j-1}-S_{i-1,j}\cap S_{i,j-1}$, где $S_{i-1,j}\cap S_{i,j-1} = S_{i-1,j-1}$. Тогда при $1 \leqslant i \leqslant n$, $1 \leqslant j \leqslant m$ вычисляем частичные суммы по формуле: $$S_{i,j} = S_{i-1,j}+S_{i,j-1}-S_{i-1,j-1}+a_{ij}.$$

Ссылки

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

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

Related Images:

e-olymp 8651. Браслети (Bangles)

14/06/2019 by Руслан Масальский

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

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

Вхідні дані

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

Вихідні дані

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

Тести

№	Inputs	Outputs
1	5 7 1 3 1 4 2 4 2 5 3 4 3 5 4 5	2
2	4 4 1 2 2 3 3 4 1 4	1
3	5 5 1 2 2 3 3 5 1 4 1 5	1

Код

#include <iostream>
using namespace std;
typedef long long ll;
const ll INF = 3e2+5;
ll arr[INF][INF];
void power(ll n){
    ll arr1[n][n];
    for(int i  = 0 ; i < n ; i++){
        for(int j = 0 ; j < n; j++){
            arr1[i][j]=0;
            for(int k = 0 ; k < n ; k ++){
                arr1[i][j]+=arr[i][k]* arr[k][j];
            }
            
        }
    }
    for(int i  = 0 ; i < n ; i++){
        for(int j = 0 ; j < n; j++){
            arr[i][j]=arr1[i][j];
        }
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,m ;
    cin>>n>>m;
    ll a,b;
    for(int i = 0 ; i < m ; i++){
        cin>>a>>b;
        a--;
        b--;
        if(a!=b){
            arr[a][b]++;
            arr[b][a]++;    
        }
    }
    power(n);
    ll to_del[n];
    for(int i = 0 ; i < n; i++){
        to_del[i]=0;
        for(int j = 0 ; j < n; j++){
            if(i==j){
                arr[i][i] = 0;
            }else{
                to_del[i]+=arr[i][j];
            }
        }
    }
    power(n);
    ll answer =0;
    for(int i = 0 ; i < n ; i++){
        answer +=arr[i][i]-to_del[i];
    }
    cout<<answer/8;
    return 0;
}

#include <iostream>

using namespace std;

typedef long long ll;

const ll INF = 3e2+5;

ll arr[INF][INF];

void power(ll n){

ll arr1[n][n];

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

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

arr1[i][j]=0;

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

arr1[i][j]+=arr[i][k]* arr[k][j];

}

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

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

arr[i][j]=arr1[i][j];

}

int main() {

ios_base::sync_with_stdio(0);

cin.tie(0);

int n,m ;

cin>>n>>m;

ll a,b;

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

cin>>a>>b;

a--;

b--;

if(a!=b){

arr[a][b]++;

arr[b][a]++;

}

power(n);

ll to_del[n];

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

to_del[i]=0;

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

if(i==j){

arr[i][i] = 0;

}else{

to_del[i]+=arr[i][j];

}

power(n);

ll answer =0;

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

answer +=arr[i][i]-to_del[i];

}

cout<<answer/8;

return 0;

}

Рішення

Зробимо ізоморфний перехід в графи, а саме можна помітити, що визначивши типи запків як вершини матимемо зв’язки між типами, як існуючий елемент браслета, тобто пара $(1, 2)$ насправді задає зв’язок між першим і другим типом. Маэмо граф, залишилось знайти кількість простих циклів завдовшки у чотири ребра (чотири вершини).
Построївши матрицю суміжності ми на справді побудували матрицю де arr[i][j] містить кількість способів дійти від вершини $i$ до вершини $j$ за один хід.
Нехай за х ходів ми потрапили з вершини $i$ у вершину $k$ рівно $a$ способами, а з вершини $k$ у вершину $j$ рівно $b$ способами. Тоді за $2x$ ходів ми можемо потрапити з вершини $i$ у вершину $j$ через вершину $k$ рівно $ab$ способами, що насправді еквівалентно возведенню матриці суміжності у степінь, яка дорівнює кількості ходів
Тепер за два перемноження отримаємо матрицю де arr[i][j] містить кількість способів дійти від вершини $i$ до вершини $j$ за 4 ходи. Сумма елементів на головній діагоналі майже дає нам потрібний результат. Нам треба відняти ходи такого типу 1-2-1-2-1 та 1-2-3-2-1. Щоб відняти ходи першого типу після першого перемноження поставимо на головній діагоналі нулі, що означатиме що ми не можемо у другому ході повернутися у ту вершину з якої прибули. Для другого типу треба помітити, що ми йдемо по тому шляху, по якому вже йшли тобто якщо мі за два ходи дійшли до певної вершини $a$ способами, то повертаючись назад отримаємо $2a$ способів, але з них рівно $a$ нам не підходять, тому після другого перемноження с діагоналі видаляємо сумму на ряді на моменті коли було зроблено усього $2$ ходи, звісно не враховуючи елементи на головній діагоналі. Ми будували неорієнтований граф тому сумму на діагоналі треба поділити на $2,$ а ще в наших циклах по $4$ вершини, тому треба ще поділити на 4.

Посилання

ideone
e-olymp

Related Images:

e-olymp 685. Сумма на параллелепипеде

10/06/2019 by Никита Шпилевский

Задача

Задана трехмерная таблица чисел [latex]a_{ijt}[/latex], где [latex]1\leq i\leq n[/latex], [latex]1\leq j\leq m[/latex], [latex]1\leq t\leq k[/latex]. Для заданных [latex]l_{x}, l_{y}, l_{z},r_{x}, r_{y}, r_{z}[/latex] найдите

[latex]S_{l_{x}, l_{y}, l_{z},r_{x}, r_{y}, r_{z}}=\sum\limits_{i=lx,j=ly,t=lz}^{i\leq rx,j\leq ry,t\leq rz}a_{ijt}[/latex]

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

В первой строке записаны размеры таблицы — [latex]n, m, k \left ( 1\leq n, m, k\leq 100 \right )[/latex]. Далее записано [latex]n[/latex] блоков по [latex]m[/latex] строк, в каждой из которых записaно по [latex]k[/latex] чисел [latex]a_{ijt} \left ( 1\leq a_{ijt} \leq 1000 \right )[/latex]. Блоки разделены пустой строкой. В очередной строке записано число [latex]q \left ( 1\leq q\leq 10^{6} \right )[/latex] — количество запросов. В следующих [latex]q[/latex] строках описаны запросы [latex]l_{x_{i}}, l_{y_{i}}, l_{z_{i}}, r_{x_{i}}, r_{y_{i}}, r_{z_{i}}[/latex][latex]\left ( 1 \leq l_{x_{i}} \leq r_{x_{i}} \leq n, 1 \leq l_{y_{i}} \leq r_{y_{i}} \leq m, 1 \leq l_{z_{i}} \leq r_{z_{i}} \leq k \right )[/latex] .

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

Выведите [latex]q[/latex] чисел в отдельных строках — ответы на запросы.

Тесты

№	Входные данные	Выходные данные
1	2 3 5 1 2 3 4 5 5 4 3 2 1 2 3 1 5 41 2 3 4 5 5 4 3 2 1 2 3 1 5 4 5 1 1 1 1 2 2 1 1 1 2 2 2 1 2 3 2 3 4 1 3 4 2 3 5 1 2 4 2 2 5	12 24 22 18 6

Код

#include <iostream>
using namespace std;
const long long INF = 105;
long long arr[INF][INF][INF];
long long amountArray[INF][INF][INF];
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n,m,k;
    cin >> n >> m >> k;
    for(int i = 1 ; i <= n; i++){
        for(int j = 1 ; j <= m ; j++){
            for(int z = 1 ; z <= k ; z++){
                cin >> arr[i][j][z];
            }
        }
    }
    for(int i  = 1 ; i <= n; i++){
        for(int j = 1; j <= m ; j++){
            amountArray[i][j][1] = amountArray[i-1][j][1] + 
                amountArray[i][j-1][1] - amountArray[i-1][j-1][1] + arr[i][j][1];
        }
    }
    for(int i  = 1 ; i <= m; i++){
        for(int j = 1; j <= k ; j++){
            amountArray[1][i][j] = amountArray[1][i-1][j] + 
                amountArray[1][i][j-1] - amountArray[1][i-1][j-1] + arr[1][i][j];
        }
    }
    for(int i  = 1 ; i <= n; i++){
        for(int j = 1; j <= k ; j++){
            amountArray[i][1][j] = amountArray[i-1][1][j] + 
                amountArray[i][1][j-1] - amountArray[i-1][1][j-1] + arr[i][1][j];
        }
    }
 
    for(int i = 2; i <= n; i++){
        for(int j = 2; j <= m ; j++){
            for(int z = 2; z <= k; z++){
                amountArray[i][j][z] = arr[i][j][z] + 
                    amountArray[i-1][j][z] + amountArray[i][j-1][z] - 
                    amountArray[i-1][j-1][z] + amountArray[i][j][z-1] - 
                    amountArray[i-1][j][z-1] - amountArray[i][j-1][z-1] + 
                    amountArray[i-1][j-1][z-1];
            }
        }
    }
    long long q;
    cin >> q;
    while(q--){
        long long x1, y1, z1, x2, y2, z2;
        cin >> x1 >> y1 >> z1 >> x2 >> y2 >> z2;
        x1--;
        y1--;
        z1--;
        cout << amountArray[x2][y2][z2] - amountArray[x2][y2][z1] - 
            amountArray[x2][y1][z2] + amountArray[x2][y1][z1] - 
            amountArray[x1][y2][z2] + amountArray[x1][y1][z2] + 
            amountArray[x1][y2][z1] - amountArray[x1][y1][z1] << "\n";
    }
    return 0;
}

#include <iostream>

using namespace std;

const long long INF = 105;

long long arr[INF][INF][INF];

long long amountArray[INF][INF][INF];

int main() {

ios_base::sync_with_stdio(0);

cin.tie(0);

cout.tie(0);

long long n,m,k;

cin >> n >> m >> k;

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

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

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

cin >> arr[i][j][z];

}

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

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

amountArray[i][j][1] = amountArray[i-1][j][1] +

amountArray[i][j-1][1] - amountArray[i-1][j-1][1] + arr[i][j][1];

}

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

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

amountArray[1][i][j] = amountArray[1][i-1][j] +

amountArray[1][i][j-1] - amountArray[1][i-1][j-1] + arr[1][i][j];

}

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

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

amountArray[i][1][j] = amountArray[i-1][1][j] +

amountArray[i][1][j-1] - amountArray[i-1][1][j-1] + arr[i][1][j];

}

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

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

for(int z = 2; z <= k; z++){

amountArray[i][j][z] = arr[i][j][z] +

amountArray[i-1][j][z] + amountArray[i][j-1][z] -

amountArray[i-1][j-1][z] + amountArray[i][j][z-1] -

amountArray[i-1][j][z-1] - amountArray[i][j-1][z-1] +

amountArray[i-1][j-1][z-1];

}

long long q;

cin >> q;

while(q--){

long long x1, y1, z1, x2, y2, z2;

cin >> x1 >> y1 >> z1 >> x2 >> y2 >> z2;

x1--;

y1--;

z1--;

cout << amountArray[x2][y2][z2] - amountArray[x2][y2][z1] -

amountArray[x2][y1][z2] + amountArray[x2][y1][z1] -

amountArray[x1][y2][z2] + amountArray[x1][y1][z2] +

amountArray[x1][y2][z1] - amountArray[x1][y1][z1] << "\n";

}

return 0;

}

Решение

Создаем массивы arr — массив элементов исходной матрицы, и amountArray — массив количества элементов «на префиксе». В первой тройке вложенных циклов for заполняем массив arr. Затем в трех парах вложенных массивов заполняем соответственно первый «этаж» матрицы amountArray, первую строку и первый столбец всех «этажей». Далее, в тройке вложенных циклов for заполняем оставшиеся элементы массива. После, читаем запросы и выводим ответы.

Ссылки

- Задача на e-olymp
- Решение на ideone

Related Images:

e-olymp 7534. Замкнутое сокровище

03/06/2019 by Алина Гук

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

Задача

Группа из $n$ бандитов спрятала украденное сокровище в комнате. Дверь в комнату следует отпереть только когда понадобится вынести сокровище. Так как бандиты не доверяют друг другу, они хотят иметь возможность открыть комнату и унести украденное только если этого захотят не менее $m$ из них.

Они решили разместить несколько замков на двери таким образом, чтобы она открывалась только когда открыты все замки. Каждый замок может иметь до $n$ ключей, распределенных среди некоторого подмножества бандитов. Группа бандитов может открыть замок, только если кто-то в группе имеет ключ к этому замку.

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

Например, если $n = 3$ и $m = 2$, то достаточно $3$ замков — ключи от замка $1$ получают бандиты $1$ и $2$, ключи от замка $2$ получают бандиты $1$ и $3$, ключи от замка $3$ получают бандиты $2$ и $3$. Ни один из бандитов не может открыть все замки самостоятельно, но любая группа из $2$ бандитов может открыть все замки. Можно убедиться, что $2$ замков для этого случая не достаточно.

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

Первая строка содержит количество тестов. Каждая следующая строка является отдельным тестом и содержит два числа $n(1 \leqslant n \leqslant 30)$ и $m(1 \leqslant m \leqslant n)$.

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

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

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	4 3 2 5 1 10 7 5 3	3 1 210 10
2	2 5 3 3 2	10 3
3	6 2 1 7 2 3 1 5 4 3 2 9 2	1 7 1 10 3 9

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

#include <iostream>
#include <cstring>
#define MAX 31
using namespace std;

int main() {
    int tests, n, m;
    long long c[MAX][MAX];
    memset(c, 0, sizeof(c));
    for(int i = 0; i < MAX; i++) c[i][0] = 1;
    for(int i = 0; i < MAX; i++)
        for(int j = 1; j <= MAX; j++)
            c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
    cin >> tests;
    while(tests--) {
        cin >> n >> m;
        cout << c[n][m - 1] << "\n";
    }
    
    return 0;
}

#include <iostream>

#include <cstring>

#define MAX 31

using namespace std;

int main() {

int tests, n, m;

long long c[MAX][MAX];

memset(c, 0, sizeof(c));

for(int i = 0; i < MAX; i++) c[i][0] = 1;

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

for(int j = 1; j <= MAX; j++)

c[i][j] = c[i - 1][j] + c[i - 1][j - 1];

cin >> tests;

while(tests--) {

cin >> n >> m;

cout << c[n][m - 1] << "\n";

}

return 0;

}

Решение

Для каждой группы из $m-1$ бандитов существует замок такой, что его могут открыть все остальные группы, кроме этой. Потому что, просто обьеденив две группы с одинаковыми замками, мы получим одну большую чем $m-1$, которая не может открыть замок. Таким образом, всего должно быть столько замков, сколько существует способов выбрать $m-1$ группу из $n$ бандитов. То есть $C_{n}^{m-1}$.

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

Ссылки

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

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

Треугольник Паскаля на Wikipedia

Related Images:

e-olymp 4749. Выручка театра

30/05/2019 by Иван Дуков

Задача

В театре [latex]n[/latex] рядов по [latex]m[/latex] мест в каждом. Даны две матрицы — в первой записаны стоимости билетов. Вторая сообщает, какие билеты проданы, а какие — нет ([latex]1[/latex] — соответствующий билет продан, [latex]0[/latex] — не продан).
Определите общую выручку от спектакля.

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

Сначала записано число [latex]n[/latex], затем число [latex]m[/latex] ([latex]n[/latex], [latex]m \leqslant 500[/latex]). После задана матрица стоимостей билетов ([latex]n[/latex] строк по [latex]m[/latex] чисел, каждое из чисел от [latex]0[/latex] до [latex]10000[/latex]). Далее задана матрица проданных билетов — снова [latex]n[/latex] строк по [latex]m[/latex] чисел.

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

Выведите общую выручку от продажи билетов.

Тесты

№	Входные данные	Выходные данные
1	3 3	25
	1 2 3
	4 5 6
	7 8 9

	1 0 1
	0 1 0
	1 0 1
2	2 2	0
	1 1
	2 2

	0 0
	0 0
3	4 5	380
	15 16 17 18 19
	19 18 17 16 15
	19 20 21 22 23
	23 22 21 20 19

	1 1 1 1 1
	1 1 1 1 1
	1 1 1 1 1
	1 1 1 1 1

Код программы с использованием одномерных массивов

#include <iostream>
using namespace std;
 
int main() {
    int x [500*500];
    int n, m;
    cin >> n >> m;
    int nm= n*m;
    for(int i = 1; i <= nm; i++){
        cin >> x[i];
    }
    int k;
    long long int v = 0;
    for(int i = 1; i <= nm; i++){
        cin >> k;
        v+= k*x[i];
    }
    cout << v << endl;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int x [500*500];

int n, m;

cin >> n >> m;

int nm= n*m;

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

cin >> x[i];

}

int k;

long long int v = 0;

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

cin >> k;

v+= k*x[i];

}

cout << v << endl;

return 0;

}

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

Описываем целочисленный одномерный массив x [500*500] для хранения матрицы стоимостей билетов. Описываем целочисленные переменные [latex]n[/latex] и [latex]m[/latex] (количество строк и столбцов матрицы) и считываем их. Описываем целочисленную переменную [latex]nm[/latex] (количество мест в зале) и инициализируем ее произведением [latex]n \cdot m[/latex]. Цикл инициализирует [latex]nm[/latex] элементов массива [latex]x[/latex]. Описываем целочисленную переменную [latex]k[/latex], которая принимает значения [latex]0[/latex] или [latex]1[/latex] (билет не продан или продан), и целочисленную переменную [latex]v[/latex] — стоимость проданных билетов ([latex]v[/latex] имеет тип long long int, так как максимальное значение, которое она может принять, составляет [latex]500 \cdot 500 \cdot 10000=2500000000[/latex]). Цикл считывает значения [latex]k[/latex] и увеличивает [latex]v[/latex] на k*x[i].

Код программы с использованием многомерных массивов

#include <iostream>
using namespace std;
 
int x[500][500];
int main(){
    int n, m, p;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> x[i][j];
    unsigned long long v = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> p;
            if (p) v += x[i][j];
        }
    }
    cout << v;
}

#include <iostream>

using namespace std;

int x[500][500];

int main(){

int n, m, p;

cin >> n >> m;

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

for (int j = 0; j < m; j++)

cin >> x[i][j];

unsigned long long v = 0;

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

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

cin >> p;

if (p) v += x[i][j];

}

cout << v;

}

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

По условию заданы количество строк [latex]n[/latex] и количество столбцов [latex]m[/latex] матрицы стоимости театральных билетов ( [latex] n,m\leqslant 500[/latex], каждое из чисел от [latex]0[/latex] до [latex]10000[/latex] ). Описываем целочисленную матрицу x[500][500]. Объявляем целочисленные переменные [latex]n[/latex] и [latex]m[/latex] и вводим их значения с клавиатуры. Считываем матрицу x. Объявляем переменную unsigned long long v = 0 — стоимость проданных билетов. Целочисленная переменная [latex]p = 1[/latex], если билет на ( [latex]i,j[/latex] )-е место продан, и [latex]p = 0[/latex] — в противном случае. Во вложенных циклах считываем значение [latex]p[/latex] из матрицы проданных билетов. Проверяем [latex]p[/latex] на положительность и увеличиваем [latex]v[/latex] на стоимость билета на ( [latex]i,j[/latex] )-е место.

Ссылки

e-olymp
ideone (код с одномерными массивами)
ideone (код с многомерными массивами)

Related Images:

e-olymp 4752. Кинотеатр

28/03/2019 by Анна Неделева

Задача

Однажды, ученики B-й школы города G решили съездить в кино. Администрация кинотеатра расположила их в зале размера n × m, который специально был подобран так, чтобы все места были заняты школьниками. Каждому посетителю кинотеатра был выдан свой номер.

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

Однако классный руководитель решил, что такая рассадка плохо влияет на поведение учащихся и пересадил их по-другому: ученики сначала занимали все первые места каждого ряда, потом все вторые места каждого ряда и т.д. (см. рисунок).

Администрация решила выяснить, сколько учащихся не поменяют своего места после пересадки.

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

В первой строке заданы числа $n$ и $m$ $(1 ≤ n, m ≤ 1000)$.

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

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

Тесты

№	Входные данные	Выходные данные
1	3 3	3
2	3 4	2
3	6 3	2
4	5 9	5
5	7 5	3

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

#include <iostream>
using namespace std;

int main() {
  int arr[1000][1000], n, m, count1 = 1, count2 = 1, result = 0;
  cin >> n >> m;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
      arr[i][j] = count1++;
  for (int j = 0; j < m; j++) {
    for (int i = 0; i < n; i++) {
      if (arr[i][j] == count2) result++;
      count2++;
    }
  }
  cout << result << "\n";
}

#include <iostream>

using namespace std;

int main() {

int arr[1000][1000], n, m, count1 = 1, count2 = 1, result = 0;

cin >> n >> m;

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

for (int j = 0; j < m; j++)

arr[i][j] = count1++;

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

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

if (arr[i][j] == count2) result++;

count2++;

}

cout << result << "\n";

}

Код программы с линейным массивом

#include <iostream>
using namespace std;
 
int main() {
  int arr[1000 * 1000], n, m, result = 0;
  cin >> n >> m;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
      arr[i * m + j] = i * m + j;
  for (int j = 0; j < m; j++) 
    for (int i = 0; i < n; i++) 
      if (arr[i * m + j] == j * n + i) result++;
  cout << result << "\n";
}

#include <iostream>

using namespace std;

int main() {

int arr[1000 * 1000], n, m, result = 0;

cin >> n >> m;

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

for (int j = 0; j < m; j++)

arr[i * m + j] = i * m + j;

for (int j = 0; j < m; j++)

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

if (arr[i * m + j] == j * n + i) result++;

cout << result << "\n";

}

Код программы без массива

#include <iostream>
using namespace std;
 
int main() {
  int n, m, result = 0;
  cin >> n >> m;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
      if (i * m + j == j * n + i) result++;
  cout << result << "\n";
}

#include <iostream>

using namespace std;

int main() {

int n, m, result = 0;

cin >> n >> m;

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

for (int j = 0; j < m; j++)

if (i * m + j == j * n + i) result++;

cout << result << "\n";

}

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

Для решения задачи проверяем значения до пересадки и после, если они совпадут соответственно, то инкрементируем счётчик. А в конце выводим результат.

Ссылки

Related Images:

e-olymp 8651. Браслети (Bangles)

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

Задача

Вхідні дані

Програма читає з першого рядка числа $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 8525. Четные отрицательные в матрице

27/02/2019 by Иван Киреев

Задача. Четные отрицательные в матрице

Задана матрица размера $n \times n$. Найдите количество и сумму ее четных отрицательных элементов.

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

Первая строка содержит число $n \left(1 \leq n \leq 100\right)$. Следующие строки содержат матрицу $n \times n$. Элементы матрицы по модулю не больше $100$.

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

Выведите в одной строке количество и сумму четных отрицательных чисел в матрице.

Тесты

№	Ввод	Вывод
1	3 4 -2 5 1 -4 -12 0 1 -3	3 -18
2	5 -100 -100 -100 -100 -100 -100 -100 -100 -100 -100 -100 -100 -100 -100 -100 -100 -100 -100 -100 -100 -100 -100 -100 -100 -100	25 -2500
3	2 0 0 0 0	0 0
4	3 -2 -1 -1 -1 -2 -1 -1 -1 -2	3 -6
5	2 6 8 12 100	0 0
6	4 -25 0 12 5 -29 47 23 15 11 100 -89 20 55 25 42 -12	1 -12
7	2 -12 -12 -12 -12	4 -48

Решение

При обработке двумерного массива я использовал один цикл длиной в $n^2$ витков.
В нём я обращался к элементам с помощью целого и остатка от деления на $n$, то есть изменял второй индекс заново через каждые $n$ элементов, увеличивая, при таком переходе, первый индекс на единицу.
Используя этот приём я избежал вложенных циклов и просматривал элементы в том же порядке, как если бы их использовал.

Код

#include <iostream>
using namespace std;

int main() {
    short n, count = 0, summ = 0, mat[100][100];
    cin >> n;
    for (int i = 0; i < n * n; i++)
        cin >> mat[i / n][i % n];
    for (int i = 0; i < n * n; i++) {
        short elem = mat[i / n][i % n];
        if (elem % 2 == 0 && elem < 0) {
            count++;
            summ += elem;
        }
    }
    cout << count << ' ' << summ;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

short n, count = 0, summ = 0, mat[100][100];

cin >> n;

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

cin >> mat[i / n][i % n];

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

short elem = mat[i / n][i % n];

if (elem % 2 == 0 && elem < 0) {

count++;

summ += elem;

}

cout << count << ' ' << summ;

return 0;

}

Related Images:

e-olymp 8530. Печать матрицы

26/02/2019 by Лиза Севастьянова

Задача

Условие

Задана матрица $n \cdot n$ — назовем ее $[1..n] \cdot [1..n]$ массивом. Для заданных $r$ и $c$ следует вывести $[1..r] \cdot [1..c]$ массив ($r$ строк и $c$ столбцов исходного массива).

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

Первая строка содержит число $n (1 \leq n \leq 100)$. Следующие строки содержат матрицу $n \cdot n$. Последняя строка содержит два числа $r$ и $c$ $(1 \leq r, c \leq n)$. Все числа в матрице не превышают по модулю $100$.

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

Выведите матрицу $r \cdot c$.

Тесты

№	Входные данные	Выходные данные
1	4 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 3 2	1 2 5 6 9 1
2	5 18 25 34 44 -43 54 65 75 85 -32 95 15 25 35 -3 -4 15 -6 37 0 44 43 23 3 -12 4 3	18 25 34 54 65 75 95 15 25 -4 15 -6
3	2 0 -1 23 69 1 1	0
4	3 1 2 3 -4 -5 -6 7 8 9 3 1	1 -4 7

Решение

Для решения данной задачи необходимо ввести в массив все имеющиеся данные и вывести необходимые, соответственно заданным параметрам. Можно использовать как одномерные массивы, так и двухмерные.
В реализации с одномерными вводим все данные в массив $n \cdot n$, а затем выводим, используя вложенные циклы. Цикл проходит от $0$ до $r$ и от $(j \cdot n)$ — первого элемент необходимой строки до $(c + j \cdot n)$ — последнего элемента. В реализации с двумерными массивами заводим все данные в один массив и после выводим необходимые.

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

#include <iostream>
using namespace std;
 
#define N 100
 
int main() {
    int n;
    cin >> n;
    int arr[N * N];
    for (int i = 0; i < n * n; i++) {
        cin >> arr[i]; 
    }
    int r, c;
    cin >> r >> c;
    for (int i = 0; i < c * r; i++) {
        cout << arr[((i / c) * n) + (i % c)] << ((1+i) % c == 0? "\n" : " ");
    }
}

#include <iostream>

using namespace std;

#define N 100

int main() {

int n;

cin >> n;

int arr[N * N];

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

cin >> arr[i];

}

int r, c;

cin >> r >> c;

for (int i = 0; i < c * r; i++) {

cout << arr[((i / c) * n) + (i % c)] << ((1+i) % c == 0? "\n" : " ");

}

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

#include <iostream>
using namespace std;
 
#define N 100
 
int main() {
    int n, r, c;
    cin >> n;
    int arr[N][N];
    for (int i = 0; i < n; i++) {
        for (int j = 0 ; j < n; j++) 
            cin >> arr[i][j];
    }
    cin >> r >> c;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cout << arr[i][j] << " ";
        } cout << endl;
    }
    return 0; 
}

#include <iostream>

using namespace std;

#define N 100

int main() {

int n, r, c;

cin >> n;

int arr[N][N];

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

for (int j = 0 ; j < n; j++)

cin >> arr[i][j];

}

cin >> r >> c;

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

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

cout << arr[i][j] << " ";

} cout << endl;

}

return 0;

}

Ссылки

Related Images:

e-olymp 7261. Трудный путь

20/02/2019 by Владислав Шеванов

Задача

Вася хорошо выпил и теперь, когда он добрался до своей улицы, он полностью потерял чувство направления. Поскольку он не помнит, с какой стороны его дом, он выбирает направление наобум. Более того, на каждом перекрёстке он с вероятностью $50\%$ продолжает идти вперёд, а иначе разворачивается и идёт назад. Он настолько потерял связь с реальностью, что может даже пройти мимо своего дома и не заметить этого!

Пройдя $n$ кварталов, Вася засыпает прямо на улице. Проснувшись, он задаётся вопросом: какой у него был шанс заснуть рядом с домом? Ведь от перекрёстка, от которого он начал свой путь, до перекрёстка рядом с домом Васи всего $m$ кварталов. Помогите ему.

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

В одной строке содержатся два целых числа $n$ и $m$ [latex](0 \le n , m \le 1000)[/latex].

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

Выведите одно число — вероятность Васи заснуть на перекрёстке рядом со своим домом. Выведите ответ с абсолютной погрешностью не более $10^{-7}$.

Тесты

Входные данные	Выходные данные
1 1	0.500000000
10 20	0.000000000
1000 100	0.000169397
16 2	0.174560547
90 44	0.000001273

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

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

int main() {
    int n, m;
    cin >> n >> m;
    double** x = new double* [n+1];
    for (int i = 0; i < n+1; i++) {
        x[i] = new double [2*n+1];
    }
    x[0][n] = 1;
    double a, b;
    for(int i = 1; i <= n; i++) {
      for(int j = n - i; j <= n + i; j++) {
        a = (j - 1 < 0)? 0 : x[i-1][j-1];
        b = (j + 1 > 2*n)? 0 : x[i-1][j+1];
        x[i][j] = (a + b) / 2;
      }
    }
    double h = (n + m > 2*n)? 0 : x[n][n+m];
    cout << fixed << setprecision(9) << h;
    for (int i = 0; i < n+1; i++) {
        delete []x[n-i];
    }
    delete []x;
    return 0;
}

#include <iostream>

#include <iomanip>

using namespace std;

int main() {

int n, m;

cin >> n >> m;

double** x = new double* [n+1];

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

x[i] = new double [2*n+1];

}

x[0][n] = 1;

double a, b;

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

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

a = (j - 1 < 0)? 0 : x[i-1][j-1];

b = (j + 1 > 2*n)? 0 : x[i-1][j+1];

x[i][j] = (a + b) / 2;

}

double h = (n + m > 2*n)? 0 : x[n][n+m];

cout << fixed << setprecision(9) << h;

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

delete []x[n-i];

}

delete []x;

return 0;

}

Решение

Закодируем путь Васи последовательностью из 0 и 1. Пусть 1 соответствует движению вправо, а 0 влево. Пусть из $n$ шагов, которые совершил Вася, $k$ шагов он сделал вправо. Тогда $n-k$ шагов он сделал влево.Нас интересует вероятность того, что Вася переместился в одну из сторон (например вправо) на $m$ кварталов. Тогда должно выполняться: $m+n-k=k$, откуда $k=\frac{m+n}{2}$.Количество последовательностей длины $n$ с $k$ единицами равно $C_n^k$. Поскольку Вася совершил $n$ перемещений, то у него имеется $2^n$ вариантов выбора различных путей. Следовательно вероятность того что Вася пройдет вправо m кварталов, равна $\frac{C_n^k}{2^n}$, где $k=\frac{m+n}{2}$. Отметим, что искомая вероятность равна 0, если $m+n$ нечетно. В этом случае Вася просто не сможет попасть домой, то есть $m+n=2k$ четно.

Ссылки

Related Images:

e-olymp 1463. На перекрёстке

29/01/2019 by Александр Мога

Задача

Дано таблицу [latex] n \times n [/latex]. Возбуждённостью строки или столбца назовём сумму чисел в нём. Необходимо определить число, находящееся на перекрёстке наиболее возбуждённой строки и наименее возбуждённого столбца. Причём, чем выше будет этот перекрёсток (а среди них левее), тем большей будет вероятность прохождения теста.

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

Первая строка входного файла содержит число [latex]n (1 \le n \le 100)[/latex], последующие $n$ строк содержат саму таблицу. Числа в таблице натуральные и не превышают $100000$.

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

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

В выходной файл выведите единственное число – ответ к задаче.

Тесты

Вход	Выход
2 4 3 2 1	3
3 1 1 1 1 1 1 1 1 1	1
4 3 2 5 8 13 32 51 9 12 22 3 17 2 1 1 5	13
2 32 19 65 11	11
3 3 9 2 13 1 0 3 1 7	2

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

#include <iostream>
using namespace std;

int main() {
    int n; 
    int mer=0;          // most excited row
    int lec=0;          // least excited column
    cin >> n;
    int **table=new int *[n];
    for (int i=0; i<n; i++)
        table[i]= new int [n];
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
            cin >> table[i][j];
    int *exc= new int [n];      // excitation of the rows / columns
    for (int l=0; l<n; l++){
        exc[l]=0;
        for (int i=0; i<n; i++)
            exc[l]+=table[l][i];
    }
    for (int i=0; i<n; i++){
        if (exc[mer] < exc[i]){
            exc[mer]=exc[i];
            mer=i;
        }
    }
    for (int k=0; k<n; k++){
        exc[k]=0;
        for (int j=0; j<n; j++)
            exc[k]+=table[j][k];
    }
    for (int i=0; i<n; i++){
        if (exc[lec] > exc[i]){
            exc[lec]=exc[i];
            lec=i;
        }
    }
    cout << table[mer][lec];
    for (int i = 0; i < n; i++) 
        delete []table[i];
    delete []table;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

int mer=0; // most excited row

int lec=0; // least excited column

cin >> n;

int **table=new int *[n];

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

table[i]= new int [n];

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

for (int j=0; j<n; j++)

cin >> table[i][j];

int *exc= new int [n]; // excitation of the rows / columns

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

exc[l]=0;

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

exc[l]+=table[l][i];

}

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

if (exc[mer] < exc[i]){

exc[mer]=exc[i];

mer=i;

}

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

exc[k]=0;

for (int j=0; j<n; j++)

exc[k]+=table[j][k];

}

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

if (exc[lec] > exc[i]){

exc[lec]=exc[i];

lec=i;

}

cout << table[mer][lec];

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

delete []table[i];

delete []table;

return 0;

}

Решение

Создаем динамический массив, в котором вводим числа.

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

Ссылки

e-olymp

ideone

Related Images:

e-olymp 1485. Серия степеней матриц

26/01/2019 by Инна Литвиненко

Задача

По заданной матрице A размера n×n и положительному целому значению $k$ вычислить сумму $S = A + A^2+ A^3 + … + A^k.$

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

Первая строка содержит три положительных целых числа $n (n ≤ 30)$, $k (k ≤ 10^9)$ и $m (m < 10^4)$. Каждая из следующих $n$ строк содержит $n$ неотрицательных целых чисел меньших $32768$, задающих элементы матрицы $A$ в порядке возрастания строк.

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

Вывести элементы матрицы $S$ по модулю $m$ в таком же виде как и входная матрица $A$.

Тесты

№	Ввод	Вывод
1	2 2 4 0 1 1 1	1 2 2 3
2	4 7 2 3 5 12 10 8 9 2 16 7	1 0 0 0 0 1 0 0 1 1 0 0 0 1 0 0
3	5 10 78 7 6 0 1 6 12 9 1 1 8 1 1 3 1 9 8 5 34 1 7 5 5 5 5 5	2 67 36 32 48 2 6 10 49 65 67 14 58 4 29 64 54 33 45 46 41 4 50 8 55
4	3 2 4 3 3 3 3 3 3 3 3 3	2 2 2 2 2 2 2 2 2
5	5 100 1000 1846 4675 8090 4539 1234 4567 7453 9564 6548 1111 5674 9876 5432 1010 1515 0 478 3 11 0 68303 7777 32767 14 8008	614 7 945 925 381 22 332 981 689 527 351 627 130 686 420 340 628 819 758 629 913 426 396 871 91

Код

#include <iostream>
using namespace std;

struct matrix {
    int mat[31][31];
};

long n, m;
matrix E; //единичная матрица

matrix mul(matrix A, matrix B) {
    matrix C;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            C.mat[i][j] = 0;
            for (int v = 0; v < n; v++)
                C.mat[i][j] += A.mat[i][v] * B.mat[v][j] % m;
        }
    return C;
}

matrix sum(matrix A, matrix B) { 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            A.mat[i][j] += B.mat[i][j] % m;
    return A;
}

matrix power(matrix A, int k) { 
    if (k == 1)
        return A;
    matrix B = power(A, k / 2);
    B = mul(B, B);
    if (k % 2 != 0)
        B = mul(B, A);
    return B;
}

matrix res(matrix A, int k) {
    if (k == 1)
        return A;
    if (k % 2 == 0) {
        matrix B = res(A, k / 2);
        return mul(sum(power(A, k / 2), E), B);
    }
    else {
        matrix B = res(A, k / 2);
        matrix C = power(A, (k + 1) / 2);
        return sum(C, mul(B, sum(C, E)));
    }
}

int main() {
    long long k;
    matrix A;
    cin >> n >> k >> m;
    for (int i = 0; i < n; i++) {
        E.mat[i][i] = 1;
        for (int j = 0; j < n; j++) 
            cin >> A.mat[i][j];
    }
    matrix ans = res(A, k);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
           if (j != 0)
                cout << " ";
            cout << ans.mat[i][j] % m;
        }
        cout << "\n";
    }
    return 0;
}

#include <iostream>

using namespace std;

struct matrix {

int mat[31][31];

};

long n, m;

matrix E; //единичная матрица

matrix mul(matrix A, matrix B) {

matrix C;

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

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

C.mat[i][j] = 0;

for (int v = 0; v < n; v++)

C.mat[i][j] += A.mat[i][v] * B.mat[v][j] % m;

}

return C;

}

matrix sum(matrix A, matrix B) {

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

for (int j = 0; j < n; j++)

A.mat[i][j] += B.mat[i][j] % m;

return A;

}

matrix power(matrix A, int k) {

if (k == 1)

return A;

matrix B = power(A, k / 2);

B = mul(B, B);

if (k % 2 != 0)

B = mul(B, A);

return B;

}

matrix res(matrix A, int k) {

if (k == 1)

return A;

if (k % 2 == 0) {

matrix B = res(A, k / 2);

return mul(sum(power(A, k / 2), E), B);

}

else {

matrix B = res(A, k / 2);

matrix C = power(A, (k + 1) / 2);

return sum(C, mul(B, sum(C, E)));

}

int main() {

long long k;

matrix A;

cin >> n >> k >> m;

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

E.mat[i][i] = 1;

for (int j = 0; j < n; j++)

cin >> A.mat[i][j];

}

matrix ans = res(A, k);

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

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

if (j != 0)

cout << " ";

cout << ans.mat[i][j] % m;

}

cout << "\n";

}

return 0;

}

Решение

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

Далее создадим функцию быстрого возведения в степень. $A^k$ представим как $\left(A^2\right)^\frac{k}{2}$ при четном $k$ и $A × \left(A^2\right)^{\frac{k — 1}{2}}$ в противном случае. Такой алгоритм позволяет значительно уменьшить количество умножений.

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

Все, что еще необходимо сделать — вывести результат по модулю $m$.

Замечание

Тесты на e-olymp требуют отсутствия пробела после последнего столбца.

Ссылки

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

Код задачи на Ideone