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

Матвей Курочкин

e-olymp 458. Черно-белая графика

24/12/2018 by Юлиана Боурош

Задача

Одна из базовых задач компьютерной графики – обработка черно-белых изображений. Изображения можно представить в виде прямоугольников шириной $w$ и высотой $h,$ разбитых на $w × h$ единичных квадратов, каждый из которых имеет либо белый, либо черный цвет. Такие единичные квадраты называются пикселами. В памяти компьютера сами изображения хранятся в виде прямоугольных таблиц, содержащих нули и единицы.

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

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

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

Первая строка содержит два целых числа $w$ и $h$ $(1 \leq w, h \leq 100).$ Последующие $h$ строк описывают первое изображение и каждая из этих строк содержит $w$ символов, каждый из которых равен нулю или единице. Далее следует описание второго изображения в аналогичном формате. Последняя строка содержит описание логической операции в виде четырех чисел, каждое из которых – ноль или единица. Первое из них есть результат применения логической операции в случае, если оба аргумента нули, второе – результат в случае, если первый аргумент ноль, второй единица, третье – результат в случае если первый аргумент единица, второй ноль, а четвертый – в случае, если оба аргумента единицы.

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

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

Тесты

	Входные данные	Выходные данные
1	5 3 01000 11110 01000 10110 00010 10110 0110	11110 11100 11110
2	2 3 010 111 000 101 1010	11 10 10
3	4 4 1111 0101 0000 1110 0011 0101 0111 1111 0011	1111 0101 0000 1110
4	3 6 100011 000111 000000 111011 001100 010101 1000	000 100 110 000 101 010

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

( использован одномерный массив)

#include <iostream>
using namespace std;

bool my_operation (bool a, bool b, bool* res) {
    if (!a and !b) return res[0];
    else if (!a and b) return res[1];
    else if (a and !b) return res[2];
    else return res[3];
}

int main() {
    int w, h, n;
    bool truth_t[4];
    cin >> w >> h;
    n = w * h;
    bool *first_t = new bool [n];
    bool *second_t = new bool [n];
    char c;
    for (int i = 0; i < n; i++) {
        cin >> c;
        first_t[i] = (c == '1' ? true : false);
    }
    for (int i = 0; i < n; i++) {
        cin >> c;
        second_t[i] = (c == '1' ? true : false);
    }
    for (int i = 0; i < 4; i++) {
        cin >> c;
        truth_t[i] = (c == '1' ? true : false);
    }
    for (int i = 0; i < n; i++) {
        if (i != 0 && i % w == 0)
        cout << endl;
        cout << my_operation(first_t[i], second_t[i], truth_t);
    }
    return 0;
}

#include <iostream>

using namespace std;

bool my_operation (bool a, bool b, bool* res) {

if (!a and !b) return res[0];

else if (!a and b) return res[1];

else if (a and !b) return res[2];

else return res[3];

}

int main() {

int w, h, n;

bool truth_t[4];

cin >> w >> h;

n = w * h;

bool *first_t = new bool [n];

bool *second_t = new bool [n];

char c;

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

cin >> c;

first_t[i] = (c == '1' ? true : false);

}

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

cin >> c;

second_t[i] = (c == '1' ? true : false);

}

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

cin >> c;

truth_t[i] = (c == '1' ? true : false);

}

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

if (i != 0 && i % w == 0)

cout << endl;

cout << my_operation(first_t[i], second_t[i], truth_t);

}

return 0;

}

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

(использован двумерный массив)

#include <iostream>
using namespace std;

bool my_operation (bool a, bool b, bool* res) {
    if (!a and !b) return res[0];
    else if (!a and b) return res[1];
    else if (a and !b) return res[2];
    else return res[3];
}

int main() {
    int w, h;
    bool truth_t[4];
    cin >> w >> h;
    bool **first_t = new bool *[h];
    bool **second_t = new bool *[h];
    for (int i = 0; i < h; i++) {
        first_t[i] = new bool [w];
        second_t[i] = new bool [w];
    }
    char c;
    for (int i = 0; i < h; i++){
        for (int j = 0; j < w; j++) {
            cin >> c;
            first_t[i][j] = (c == '1' ? true : false);
        }
    }
    for (int i = 0; i < h; i++){ 
        for (int j = 0; j < w; j++) {
            cin >> c;
            second_t[i][j] = (c == '1' ? true : false);
        }
    }
    for (int i = 0; i < 4; i++) {
        cin >> c;
        truth_t[i] = (c == '1' ? true : false);
    }
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cout << my_operation(first_t[i][j], second_t[i][j], truth_t);
        }
        if (i < h - 1) cout << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

bool my_operation (bool a, bool b, bool* res) {

if (!a and !b) return res[0];

else if (!a and b) return res[1];

else if (a and !b) return res[2];

else return res[3];

}

int main() {

int w, h;

bool truth_t[4];

cin >> w >> h;

bool **first_t = new bool *[h];

bool **second_t = new bool *[h];

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

first_t[i] = new bool [w];

second_t[i] = new bool [w];

}

char c;

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

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

cin >> c;

first_t[i][j] = (c == '1' ? true : false);

}

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

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

cin >> c;

second_t[i][j] = (c == '1' ? true : false);

}

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

cin >> c;

truth_t[i] = (c == '1' ? true : false);

}

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

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

cout << my_operation(first_t[i][j], second_t[i][j], truth_t);

}

if (i < h - 1) cout << endl;

}

return 0;

}

Решение

Объявляем два булевых динамических массива под две пиксельные таблицы и один статический для таблицы истинности, вводим входные данные. Затем поочерёдно сравниваем соответствующие элементы массивов с помощью функции my_operation, которая принимает две переменные a и b булевского типа и булев массив res с таблицей истинности, и возвращает соответствующее значение из таблицы для комбинации значений a и b. Результат сравнения выводим.

Ссылки

Одномерный массив
- ideone.com
- e-olymp.com
Двумерный массив
- ideone.com
- e-olymp.com

Юлиана Боурош

e-olymp 54. Мурзик

27/06/2018 by Данилов Андрей

Задача

Весна… Прекрасное время! Все, казалось бы оживает и двигается, расцветает, начинается новый проход цикла жизни. И общеизвестный Мурзик не является исключением! Но если он чрезвычайно активен днем – то точно так же крепко спит ночью. Причем несчастный хищник видит преимущественно кошмары…

Одной ночью ему приснилось, что он судья на математических соревнованиях крыс (да, в наш век цифровых технологий даже крысы не остаются за гранью научно-технического прогресса). Соревнования проводятся среди [latex]N[/latex] команд по [latex]K[/latex] крыс в каждой. Соревнования проводятся в [latex]К[/latex] раундов, в каждом из которых представитель команды называет число. Побеждает та команда, у которой произведение всех чисел наибольшее. Почему крысы не называют каждый раз максимально возможное число? На то они и крысы, что в отличии от Мурзика, обделены интеллектом. Но и Мурзик понимает, что сам подсчитать результат не сможет из-за недостачи математических способностей и поэтому просит вашей помощи.

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

Первая строка содержит два целых числа [latex]N[/latex] и [latex]K[/latex] [latex](0 < N ≤ 20, 0 < K ≤ 100000)[/latex]. Следующие [latex]K[/latex] строк содержат по N чисел, которые называют представители команд. Причем крысы, как представители образованного вида, знают только 32-битовые знаковые числа.

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

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

Тесты

#	Входные данные	Выходные данные
1	3 3 20 10 30 15 20 20 30 30 20	3
2	3 3 20 -10 -30 15 25 20 30 -30 20	1
1	3 3 0 -10 -30 15 25 20 30 -30 20	2

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

#include <iostream>
#include <cmath>
#include <climits>

using namespace std;

double INF = 1e18;

int sgn(long long a){
    if(a < 0) return -1;
    else if(a == 0) return 0;
    else return 1;
}

struct logNumber{
    long long sign;
    double value;
    logNumber(int sign = 1, double value = 0){
        this->sign = sign;
        this->value = value;
    }
    void operator *= (long long a){
        sign *= sgn(a);
        if(sign == 0) value = 0;
        else value += log(abs(a));
    }
    bool operator >(logNumber a){
        return (sign > a.sign) or  (sign == 1 and a.sign == 1 and value > a.value) or (sign == -1 and a.sign == -1 and value < a.value);
    }
    bool operator ==(logNumber a){
        return sign == a.sign and value == a.value;
    }
};

int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int n,k;
    cin>>n>>k;
    logNumber mult[n];
    for(int i =0; i < k; i++){
        for(int j=0; j < n; j++){
            long long temp;
            cin>>temp;
            mult[j] *= temp;
        }
    }
    logNumber maxMult = mult[0];
    int maxTeam = 0;
    for(int i = 0; i < n; i++){
        if (mult[i] > maxMult){
            maxMult = mult[i];
            maxTeam = i;
        }
        else if(mult[i]==maxMult){
            maxTeam = max(i, maxTeam);
        }
    }
    cout << maxTeam + 1;




    return 0;
}

#include <iostream>

#include <cmath>

#include <climits>

using namespace std;

double INF = 1e18;

int sgn(long long a){

if(a < 0) return -1;

else if(a == 0) return 0;

else return 1;

}

struct logNumber{

long long sign;

double value;

logNumber(int sign = 1, double value = 0){

this->sign = sign;

this->value = value;

}

void operator *= (long long a){

sign *= sgn(a);

if(sign == 0) value = 0;

else value += log(abs(a));

}

bool operator >(logNumber a){

return (sign > a.sign) or (sign == 1 and a.sign == 1 and value > a.value) or (sign == -1 and a.sign == -1 and value < a.value);

}

bool operator ==(logNumber a){

return sign == a.sign and value == a.value;

}

};

int main() {

cin.tie(NULL);

ios_base::sync_with_stdio(false);

int n,k;

cin>>n>>k;

logNumber mult[n];

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

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

long long temp;

cin>>temp;

mult[j] *= temp;

}

logNumber maxMult = mult[0];

int maxTeam = 0;

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

if (mult[i] > maxMult){

maxMult = mult[i];

maxTeam = i;

}

else if(mult[i]==maxMult){

maxTeam = max(i, maxTeam);

}

cout << maxTeam + 1;

return 0;

}

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

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

Ссылки

Ссылка на e-olymp
Ссылка на ideone

Данилов Андрей

e-olymp 1482. Умножение матриц

25/06/2018 by Томас Пасенченко

Задача

Пусть даны две прямоугольные матрицы $A$ и $B$ размерности $m \times n$ и $n \times q$ соответственно:
$$A = \begin{bmatrix} a_{11} & a_{12} & \ldots & a_{1n} \\ a_{21} & a_{22} & \ldots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \ldots & a_{mn} \end{bmatrix} \; , \; B = \begin{bmatrix} b_{11} & b_{12} & \ldots & b_{1q} \\ b_{21} & b_{22} & \ldots & b_{2q} \\ \vdots & \vdots & \ddots & \vdots \\ b_{n1} & b_{n2} & \ldots & b_{nq} \end{bmatrix} .$$
Тогда матрица $C$ размерностью $m \times q$ называется их произведением:
$$C = \begin{bmatrix} c_{11} & c_{12} & \ldots & c_{1q} \\ c_{21} & c_{22} & \ldots & c_{2q} \\ \vdots & \vdots & \ddots & \vdots \\ c_{m1} & c_{m2} & \ldots & c_{mq} \end{bmatrix} ,$$
где: $$c_{i,j} = \sum_{r=1}^{n} a_{i,r}b_{r,j} \; \left(i = 1, 2, \ldots m; j = 1, 2, \ldots q\right).$$
Операция умножения двух матриц выполнима только в том случае, если число столбцов в первом сомножителе равно числу строк во втором; в этом случае говорят, что форма матриц согласована.

Задано две матрицы $A$ и $B$. Найти их произведение.

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

В первой строке задано $2$ натуральных числа $n_a$ и $m_a$ – размерность матрицы $A$. В последующих $n_a$ строках задано по $m_a$ чисел – элементы $a_{ij}$ матрицы $A$. В $\left(n_a + 2\right)$-й строке задано $2$ натуральных числа $n_b$ и $m_b$ – размерность матрицы $B$. В последующих $n_b$ строках задано по $m_b$ чисел – элементы $b_{ij}$ матрицы $B$. Размерность матриц не превышает $100 \times 100$, все элементы матриц целые числа, не превышающие по модулю $100$.

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

В первой строке вывести размерность итоговой матрицы $C$: $n_с$ и $m_c$. В последующих $n_с$ строках вывести через пробел по $m_c$ чисел – соответствующие элементы $c_{ij}$ матрицы $C$. Если умножать матрицы нельзя — в первой и единственной строке вывести число $\; -1$.

Тесты

Входные данные	Выходные данные
2 3 1 3 4 5 -2 3 3 3 1 3 2 2 1 3 0 -1 1	2 3 7 2 15 1 10 7
3 3 1 5 3 2 6 1 7 -1 -3 3 2 3 6 -1 1 3 1	3 2 7 14 3 19 13 38
4 4 4 8 -18 16 3 7 14 -42 2 1 1 7 4 9 5 -2 4 4 1 0 0 0 0 1 0 0 0 0 1 0	4 4 4 8 -18 16 3 7 14 -42 2 1 1 7 4 9 5 -2
3 3 5 7 -1 8 9 3 0 -6 17 2 3 7 -15 1 8 8 2	-1
2 3 57 -49 31 89 11 -37 3 1 19 -19 0	2 1 2014 1482

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

#include <iostream>
using namespace std;

int main() {
    int na, ma, nb, mb;
    cin >> na >> ma;
    int **a = new int *[na];
    for (int i = 0; i < na; i++) {
        a[i] = new int[ma];
    }
    for (int i = 0; i < na; i++) {
        for (int j = 0; j < ma; j++) {
            cin >> a[i][j];
        }
    }
    cin >> nb >> mb;
    // Проверяем возможность вычисления произведения матриц
    if (ma != nb) {
        cout << -1;
        return 0;
    }
    int **b = new int *[nb];
    for (int i = 0; i < nb; i++) {
        b[i] = new int[mb];
    }
    for (int i = 0; i < nb; i++) {
        for (int j = 0; j < mb; j++) {
            cin >> b[i][j];
        }
    }
    
    int **c = new int *[na];
    for (int i = 0; i < na; i++) {
        c[i] = new int[mb];
    }
    // Вычисляем произведение
    for (int i = 0; i < na; i++) {
        for (int j = 0; j < mb; j++) {
            for (int r = 0; r < ma; r++) {
                c[i][j] += a[i][r] * b[r][j];
            }
        }
    }
    // Выводим результат
    cout << na << " " << mb << "\n";
    for (int i = 0; i < na; i++) {
        for (int j = 0; j < mb; j++) {
            cout << c[i][j];
            if (j + 1 != mb) cout << " ";
        }
        cout << "\n";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int na, ma, nb, mb;

cin >> na >> ma;

int **a = new int *[na];

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

a[i] = new int[ma];

}

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

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

cin >> a[i][j];

}

cin >> nb >> mb;

// Проверяем возможность вычисления произведения матриц

if (ma != nb) {

cout << -1;

return 0;

}

int **b = new int *[nb];

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

b[i] = new int[mb];

}

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

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

cin >> b[i][j];

}

int **c = new int *[na];

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

c[i] = new int[mb];

}

// Вычисляем произведение

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

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

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

c[i][j] += a[i][r] * b[r][j];

}

// Выводим результат

cout << na << " " << mb << "\n";

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

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

cout << c[i][j];

if (j + 1 != mb) cout << " ";

}

cout << "\n";

}

return 0;

}

Решение

Для начала, считываем данные матрицы $A$ из входного потока и записываем их в двумерный динамический массив. Далее, получив данные о размерности второй матрицы, мы можем определить, выполнима ли операция умножения, и если нет, то прервать выполнение программы. Если операция умножения данных матриц выполнима, то считываем и записываем данные второй матрицы, после чего, по приведённой выше формуле вычисляем произведение матриц $C = A \times B.$ Наконец, выводим полученную матрицу $C.$

Ссылки

Условие задачи на e-olymp
Код задачи на ideone
Умножение матриц на Wikipedia

Томас Пасенченко

e-olymp 2669. Поворот

11/06/2018 by Иван Мясоедов

Поворот

Дан массив [latex]n[/latex] × [latex]m[/latex]. Требуется повернуть его по часовой стрелке на [latex]90[/latex] градусов.

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

В первой строке даны натуральные числа [latex]n[/latex] и [latex]m[/latex] [latex](1 ≤ n, m ≤ 50)[/latex]. На следующих [latex]n[/latex] строках записано по [latex]m[/latex] неотрицательных чисел, не превышающих [latex]109[/latex] — сам массив.

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

Выведите перевернутый массив в формате входных данных.

Тесты

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

ВХОДНЫЕ ДАННЫЕ

ВЫХОДНЫЕ ДАННЫЕ

2 2

1 2

3 4

2 2

3 1

4 2

3 3

1 2 3

4 5 6

7 8 9

3 3

4 7 1

8 5 2

9 6 3

3 4

4 5 7 8

3 6 8 7

2 2 4 5

4 3

2 3 4

2 6 5

4 8 7

5 7 8

1 2

5 4

2 1

1 1

#include <iostream>
using namespace std;

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

#include <iostream>

using namespace std;

int main() {

int n, m;

cin >> n >> m;

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

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

x[i] = new int[m];

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

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

cin >> x[i][j];

cout << m << " " << n;

cout << endl;

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

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

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

cout << endl;

}

return 0;

}

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

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

Задача на сайте e-olymp
Код решения в Ideone

Иван Мясоедов

e-olymp 2671. Сапер

10/06/2018 by Андрей Святозар Чернецкий

Задача

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

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

Даны числа $N$ и $M$ (целые, положительные, не превышают $32$) — количество строк и столбцов в поле соответственно, далее число $W$ (целое, неотрицательное, не больше $100$) — количество мин на поле, далее следует $W$ пар чисел, координаты мины на поле (первое число — строка, второе число — столбец).

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

Требуется вывести на экран поле. Формат вывода указан в примере.

Тесты

Входные данные	Выходные данные
3 2 2 1 1 2 2	* 2 2 * 1 1
2 2 0	0 0 0 0
10 10 5 1 1 3 3 5 5 7 7 9 9	* 1 0 0 0 0 0 0 0 0 1 2 1 1 0 0 0 0 0 0 0 1 * 1 0 0 0 0 0 0 0 1 1 2 1 1 0 0 0 0 0 0 0 1 * 1 0 0 0 0 0 0 0 1 1 2 1 1 0 0 0 0 0 0 0 1 * 1 0 0 0 0 0 0 0 1 1 2 1 1 0 0 0 0 0 0 0 1 * 1 0 0 0 0 0 0 0 1 1 1
1 1 1 1 1	*
32 32 10 1 1 2 2 4 4 4 3 3 4 5 5 27 28 30 30 22 31 32 32	* 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 * 2 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 4 * 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 * * 3 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 * 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 * 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 * 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 * 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 *

#include <iostream>
using namespace std;
 
int main(){
    int n, m, bomb, count = 0;
    cin >> n >> m >> bomb;
    char A[34][34];
    int x, y;
    for (int i = 0; i < n + 2; i++){ 
        for (int j = 0; j < m + 2; j++){ 
            A[i][j] = '0';
        }
    }
    for (int i = 0; i < bomb; i++){
        cin >> x >> y;
        A[x][y] = '*';
    }
    for (int i = 1; i < n + 1; i++){
        for (int j = 1; j < m + 1; j++){ 
            if (A[i][j] != '*'){
                if (A[i-1][j] == '*') count++;
                if (A[i-1][j-1] == '*') count++;
                if (A[i-1][j+1] == '*') count++;
                if (A[i+1][j+1] == '*') count++;
                if (A[i+1][j-1] == '*') count++;
                if (A[i+1][j] == '*') count++;
                if (A[i][j-1] == '*') count++;
                if (A[i][j+1] == '*') count++;
                cout << count;
                count = 0;
            }
            else cout << A[i][j];
            if (j != m) cout << " ";
        }
        cout << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main(){

int n, m, bomb, count = 0;

cin >> n >> m >> bomb;

char A[34][34];

int x, y;

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

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

A[i][j] = '0';

}

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

cin >> x >> y;

A[x][y] = '*';

}

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

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

if (A[i][j] != '*'){

if (A[i-1][j] == '*') count++;

if (A[i-1][j-1] == '*') count++;

if (A[i-1][j+1] == '*') count++;

if (A[i+1][j+1] == '*') count++;

if (A[i+1][j-1] == '*') count++;

if (A[i+1][j] == '*') count++;

if (A[i][j-1] == '*') count++;

if (A[i][j+1] == '*') count++;

cout << count;

count = 0;

}

else cout << A[i][j];

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

}

cout << endl;

}

return 0;

}

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

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

Ссылки

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

код задачи на ideone

Андрей Святозар Чернецкий

e-olymp 2261. Защита королевства

20/05/2018 by Иван Мясоедов

Защита королевства

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

Штрафом положения является количество клеток в крупнейшем незащищенном прямоугольнике. Например, положение, показанное на рисунке имеет штраф [latex]12[/latex].
Помогите Теодору написать программу, вычисляющую штраф в заданной позиции.

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

Первая строка содержит три целых числа: [latex]w[/latex] — ширина сетки, [latex]h[/latex] — высота сетки и [latex]n[/latex] — количество арбалетных башен [latex](1 ≤ w, h ≤ 40000; 0 ≤ n ≤ min(w, h))[/latex].

Каждая из следующих n строк содержит два целых числа [latex]x_i[/latex] и [latex] y_i[/latex] — координаты клетки с башней [latex](1 ≤ x_i ≤ w; 1 ≤ y_i ≤ h)[/latex].

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

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

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	10 10 3 1 1 2 2 3 3	49
2	15 15 4 4 4 5 5 7 8 13 15	30
3	30 30 5 13 14 16 27 29 30 5 5 10 15	132
4	100 100 2 1 1 100 100	9604
5	3 3 3 1 1 2 2 3 3	0

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

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

int main() {
    int x_max, y_max, n, a=0, b=0;
    cin>>x_max>>y_max>>n;
    int *x=new int[n+2];
    int *y=new int[n+2];
    for(int i=1;i<n+1;i++) 
       cin>>x[i]>>y[i];
    x[0] = y[0] = 0;
    x[n+1] = x_max + 1; 
    y[n+1] = y_max + 1;
    sort(x, x + n+1);
    sort(y, y + n+1);
    for(int i=0; i<n+1; i++){ 
       if(x[i+1]-x[i]>a) a=x[i+1]-x[i];
       if(y[i+1]-y[i]>b) b=y[i+1]-y[i];
    }
    cout<<(a-1)*(b-1);
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

int x_max, y_max, n, a=0, b=0;

cin>>x_max>>y_max>>n;

int *x=new int[n+2];

int *y=new int[n+2];

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

cin>>x[i]>>y[i];

x[0] = y[0] = 0;

x[n+1] = x_max + 1;

y[n+1] = y_max + 1;

sort(x, x + n+1);

sort(y, y + n+1);

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

if(x[i+1]-x[i]>a) a=x[i+1]-x[i];

if(y[i+1]-y[i]>b) b=y[i+1]-y[i];

}

cout<<(a-1)*(b-1);

return 0;

}

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

Алгоритм решения задачи состоит в том, чтобы найти максимальное количество незащищенных клеток между соседними башнями по координатам абсцисс и ординат (которые будет на [latex]1[/latex] меньше чем сама разность координат) и перемножить полученные числа тем самым найдя площадь образованного ими прямоугольника.

Для решения данной задачи нужно создать два массива в [latex]x[/latex] и [latex]y[/latex] (в первом будут находится [latex]x_i[/latex] координаты, а во втором [latex]y_i[/latex]) размера на [latex]2[/latex] больше чем количество заданных башен, так как нужно учитывать рамки поля, для чего достаточно добавить две башни c координатами [latex]\left(0;0\right)[/latex] и [latex]\left(x_{max}+1; y_{max}+1\right).[/latex] Далее нужно отсортировать эти массивы и найти максимальную разность между соседними элементами ([latex]a[/latex] — максимальная разность между [latex]x_i[/latex] элементами, [latex]b[/latex] — максимальная разность между [latex]y_i[/latex]). Далее, по формуле [latex]\left(a-1\right)\cdot\left(b-1\right)[/latex] находим площадь самого большого незащищенного прямоугольника, которая равна количеству клеток в нем, что и является ответом задачи.

Задача на сайте e-olymp
Код решения в Ideone

Иван Мясоедов

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.

Эммануил Прокопов

e-olymp 1521. Оптимальное умножение матриц

07/05/2017 by Тимур Фирсов

Задача

Имея два двумерных массива [latex]A[/latex] и [latex]B[/latex], мы можем вычислить [latex]C = AB[/latex] используя стандартные правила умножения матриц. Число колонок в массиве [latex]A[/latex] должно совпадать с числом строк массива [latex]B[/latex]. Обозначим через [latex]rows(A)[/latex] и [latex]columns(A)[/latex] соответственно количество строк и колонок в массиве [latex]A[/latex]. Количество умножений, необходимых для вычисления матрицы [latex]C[/latex] (ее количество строк совпадает с [latex]A[/latex], а количество столбцов с [latex]B[/latex]) равно [latex]rows(A) columns(B) columns(A)[/latex]. По заданной последовательности перемножаемых матриц следует найти оптимальный порядок их умножения. Оптимальным называется такой порядок умножения матриц, при котором количество элементарных умножений минимально.

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

Каждый тест состоит из количества [latex]n (n ≤ 10)[/latex] перемножаемых матриц, за которым следуют [latex]n[/latex] пар целых чисел, описывающих размеры матриц (количество строк и столбцов). Размеры матриц задаются в порядке их перемножения. Последний тест содержит [latex]n = 0[/latex] и не обрабатывается.

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

Пусть матрицы пронумерованы [latex]A_{1}[/latex], [latex]A_{2}[/latex],…, [latex]A_{n}[/latex]. Для каждого теста в отдельной строке следует вывести его номер и скобочное выражение, содержащее оптимальный порядок умножения матриц. Тесты нумеруются начиная с [latex]1[/latex]. Вывод должен строго соответствовать формату, приведенному в примере. Если существует несколько оптимальных порядков перемножения матриц, выведите любой из них.

Тесты

№	Входные данные	Выходные данные
1	3 1 5 5 20 20 1 3 5 10 10 20 20 35 6 30 35 35 15 15 5 5 10 10 20 20 25 0	Case 1: (A1 x (A2 x A3)) Case 2: ((A1 x A2) x A3) Case 3: ((A1 x (A2 x A3)) x ((A4 x A5) x A6))
2	10 653 273 273 692 692 851 851 691 691 532 532 770 770 690 690 582 582 519 519 633 0	Case 1: (A1 x ((((((((A2 x A3) x A4) x A5) x A6) x A7) x A8) x A9) x A10))
3	2 11 12 12 33 7 1 5 5 28 28 19 19 2 2 10 10 1 1 12 4 10 29 29 133 133 8 8 15 0	Case 1: (A1 x A2) Case 2: (((((A1 x A2) x A3) x A4) x (A5 x A6)) x A7) Case 3: ((A1 x (A2 x A3)) x A4)

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

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

int n;
vector <int> v;
void f(long long **a, long long i, long long j ){
    if(a[j][i]>0){
        v.push_back(a[j][i]);
        if((a[j][i]<=n)&&(i<=n)&&(j<=n)){
            f(a,i,a[j][i]);
            f(a,a[j][i],j);
        }
    }
}
string answer(long long x, long long si, long long sj, long long el){
     long long z1=el,z2=el;
     if(sj!=si){
        if(si!=x){
            while((v[v.size()-z1]<si)||(v[v.size()-z1]>=x))z1++;
        }
        if(sj!=(x+1)){
            while((v[v.size()-z2]<(x+1))||(v[v.size()-z2]>=sj))z2++; 
        }
     }
    return si==sj? "A"+to_string(si):"("+answer(v[v.size()-z1],si,x,z1+1)+" x "+answer(v[v.size()-z2],x+1,sj,z2+1)+")";
}
int main() {
    long long i,j,useless,number=1,**dp;
    cin>>n;
    while(n){
        n++;
        dp = new long long* [n];
        for(i=0;i<n;i++)dp[i]=new long long [n];
        for(i=0;i<n;i++){
            for(j=0;j<n;j++){
                dp[i][j]=0;
            }
        }
        cin>>dp[0][0];
        for(i=1;i<n;i++){
            cin>>dp[i][i];
            if(i<(n-1))cin>>useless;//лишние для нас значения
        }
        i=2;
        for(i=2;i<n;i++){        
            for(j=0;j<=(i-2);j++){
                dp[i][j]=2e10;
            }
        }
        long long t;
        for(i=2;i<n;i++){
            for(j=0;j<(n-i);j++){
                long long k=j+i;
                for(t=1;(j+t)<(n-1);t++){
                    if(dp[k][j]>(dp[k][j+t]+dp[j+t][j]+dp[k][k]*dp[j][j]*dp[j+t][j+t])){
                        dp[k][j]=dp[k][j+t]+dp[j+t][j]+dp[k][k]*dp[j][j]*dp[j+t][j+t];
                        dp[j][k]=j+t;//запоминаем последнее умножение
                    }
                }
            }
        }
        f(dp,n-1,0);//восстанавливаем порядок умножений (от последнего к первому)
        reverse(v.begin(),v.end());
        cout<<"Case "<<number<<": "<<answer(v[v.size()-1],1,n-1,1)<<'\n';
        number++;
        delete [] dp;//очищаем память для следующего теста
        v.clear();
        cin>>n;
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <string>

#include <algorithm>

using namespace std;

int n;

vector <int> v;

void f(long long **a, long long i, long long j ){

if(a[j][i]>0){

v.push_back(a[j][i]);

if((a[j][i]<=n)&&(i<=n)&&(j<=n)){

f(a,i,a[j][i]);

f(a,a[j][i],j);

}

string answer(long long x, long long si, long long sj, long long el){

long long z1=el,z2=el;

if(sj!=si){

if(si!=x){

while((v[v.size()-z1]<si)||(v[v.size()-z1]>=x))z1++;

}

if(sj!=(x+1)){

while((v[v.size()-z2]<(x+1))||(v[v.size()-z2]>=sj))z2++;

}

return si==sj? "A"+to_string(si):"("+answer(v[v.size()-z1],si,x,z1+1)+" x "+answer(v[v.size()-z2],x+1,sj,z2+1)+")";

}

int main() {

long long i,j,useless,number=1,**dp;

cin>>n;

while(n){

n++;

dp = new long long* [n];

for(i=0;i<n;i++)dp[i]=new long long [n];

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

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

dp[i][j]=0;

}

cin>>dp[0][0];

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

cin>>dp[i][i];

if(i<(n-1))cin>>useless;//лишние для нас значения

}

i=2;

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

for(j=0;j<=(i-2);j++){

dp[i][j]=2e10;

}

long long t;

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

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

long long k=j+i;

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

if(dp[k][j]>(dp[k][j+t]+dp[j+t][j]+dp[k][k]*dp[j][j]*dp[j+t][j+t])){

dp[k][j]=dp[k][j+t]+dp[j+t][j]+dp[k][k]*dp[j][j]*dp[j+t][j+t];

dp[j][k]=j+t;//запоминаем последнее умножение

}

f(dp,n-1,0);//восстанавливаем порядок умножений (от последнего к первому)

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

cout<<"Case "<<number<<": "<<answer(v[v.size()-1],1,n-1,1)<<'\n';

number++;

delete [] dp;//очищаем память для следующего теста

v.clear();

cin>>n;

}

return 0;

}

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

Решение

Пусть [latex]A[/latex]- любая не последняя матрица заданной последовательности, [latex]B[/latex] — матрица, что следует за [latex]A[/latex] в данной последовательности перемножаемых матриц. Заведём двумерный массив [latex]dp[/latex] размером [latex] {(n+1)}\times {(n+1)}[/latex]. По главной диагонали массива запишем размеры матриц, причём [latex]rows(B)[/latex] не будем записывать, так как [latex]rows(B)=columns(A)[/latex]. В dp[k][j] [latex]\left( j<k \right) [/latex] будем хранить минимальное количество операций необходимое для получения матрицы [latex]C_{kj}[/latex] такой, что [latex]columns(C_{kj})[/latex] равно элементу dp[k][k], а [latex]rows(C_{kj})[/latex] соответственно dp[j][j]. Для получения матрицы [latex]C_{kj}[/latex] нужно умножить матрицу [latex]C_{k(j+t)}[/latex] на [latex]C_{(j+t)j}[/latex] [latex](\left( k-j \right) >t>0)[/latex], для этого нам понадобиться [latex]rows(C_{k(j+t)}) columns(C_{(j+t)j}) columns(C_{k(j+t)}) [/latex], что равно dp[k][k]*dp[j][j]*dp[j+t][j+t], операций непосредственно на перемножение этих матриц, а также dp[k][j+t] и dp[j+t][j] операций для получения матриц [latex]C_{k(j+t)}[/latex] и [latex]C_{(j+t)j}[/latex] соответственно.
Тогда dp[k][j]=dp[k][j+t]+dp[j+t][j]+dp[k][k]*dp[j][j]*dp[j+t][j+t]. При помощи цикла подберём [latex] t [/latex], при котором значение dp[k][j] выходит минимальным. Для получения матриц, которые даны изначально, не требуется ни одной операции, поэтому диагональ массива прилегающую к главной диагонали оставим заполненной нулями. Далее, при помощи вложенных циклов на каждом шаге внешнего цикла будем заполнять диагональ массива, что расположена ниже предыдущей. Параллельно будем запоминать номер последнего умножения, который будет равен [latex]j+t[/latex], в элемент массива, который расположен симметрично dp[k][j] относительно главной диагонали (то есть в dp[j][k]). Таким образом от умножения двух исходных матриц поэтапно перейдём к оптимальному произведению [latex]n[/latex] матриц. Затем, рекурсивно восстановим оптимальный порядок умножения матриц. Для вывода ответа в соответствующем формате также воспользуемся рекурсией.

Ссылки

Тимур Фирсов

А406

18/12/2015 by Сабиров Ильдар

Задача

С помощью [latex]x_{ij}, i=1,2; j=1,\ldots,n.[/latex] — действительной матрицы на плоскости задано n точек так, что [latex]x_{1j}, x_{2j}[/latex] — координаты [latex]j[/latex] — точки. Точки попарно соединены отрезками. Найти длину наибольшего отрезка.

Тест

n	Матрица [latex]x_{ij}, i=1,2.[/latex]	Длина наибольшего отрезка	Комментарий
3	2 8 4 9 1 5	10	Пройдено
4	6 14 2 1 9 3 8 0	13.3417	Пройдено
5	1 8 4 3 7 2 9 5 0 11	11.7047	Пройдено

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

#include <iostream>
#include <cmath>
using namespace std;
int main() 
{
	double max = 0;
	int K=2,L,x=0,y=1;
	cin >> L;
	int D[K][L];
	for (int i = 0; i < K; i++)
	{
		for (int j = 0; j < L; j++)
		{
			cin>>D[i][j];
		}
	}
	for (int i = 0; i < L-1; i++)
	{
		for (int j = 0; j < L; j++)
		{
			double q=sqrt((D[x][i]-D[x][j])*(D[x][i]-D[x][j])+(D[y][i]-D[y][j])*(D[y][i]-D[y][j]));
			if(q>max)
			{
				max=q;
			}
		}
	}
	for (int i = 0; i < K; i++)
	{
		for (int j = 0; j < L; j++)
		{
			cout<<D[i][j]<<" ";
		}
		cout<<"\n";
	}
	cout<<max;
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

double max = 0;

int K=2,L,x=0,y=1;

cin >> L;

int D[K][L];

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

{

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

{

cin>>D[i][j];

}

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

{

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

{

double q=sqrt((D[x][i]-D[x][j])*(D[x][i]-D[x][j])+(D[y][i]-D[y][j])*(D[y][i]-D[y][j]));

if(q>max)

{

max=q;

}

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

{

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

{

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

}

cout<<"\n";

}

cout<<max;

return 0;

}

Ход решения:

Вводим матрицу построчно (не очень удобно).
Находим длину наибольшего отрезка.
С помощью вложенных циклов мы находим длины всех отрезков по формуле
[latex] AB=\sqrt{(x_{2}-x_{1})^{2}+(y_{2}-y_{1})^{2}}, A(x_{1},y_{1}), B(x_{2},y_{2}). [/latex]
По алгоритму нахождения максимума находим длину наибольшего отрезка.
Выводим матрицу.
Выводим длину наибольшего отрезка.
Ссылка на код

Сабиров Ильдар

А694а

14/09/2015 by Сабиров Ильдар

Задача: Получить квадратную матрицу порядка [latex]n[/latex] [latex]\begin{pmatrix}1 &0 &\cdots & 0 \\ 0 & 1 &\cdots &0 \\ \cdots &\cdots &\cdots \cdots & \cdots \\ 0 & 0 & \cdots & 1\end{pmatrix}[/latex]

Тесты:

n	Матрица
3	1 0 0 0 1 0 0 0 1
4	1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1
6	1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1

#include <iostream>
using namespace std;

int main() {
	int n;
	cin >> n;
    int m[n][n];
    for(int i=0;i<n;i++)
    {
    	m[i][i]=1;
    }
    for(int i=0;i<n;i++)
    {
    	for(int y=0;y<n;y++)
        {
    	    if(m[i][y]!=1)
    	    {
    		    m[i][y]=0;
    	    }
        }
    }
    for(int i=0;i<n;i++)
    {
    	for(int y=0;y<n;y++)
        {
        	cout<<m[i][y]<<" ";
        }
        cout<<"\n";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

int m[n][n];

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

{

m[i][i]=1;

}

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

{

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

{

if(m[i][y]!=1)

{

m[i][y]=0;

}

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

{

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

{

cout<<m[i][y]<<" ";

}

cout<<"\n";

}

return 0;

}

Ход работы:
1. С помощью цикла заполняем главную диагональ единицами.

2. Приравниваем элементы не равные единице к нулю.

3. Вывод массива.

Ссылка на код

Сабиров Ильдар

А1035

28/06/2015 by Ковальський Олександр Дмитрович

Задача. Указать маршрут коня. Начинающегося на одном заданном поле шахматной доски и оканчивающемся на другом. Никакое поле не должно встречаться в маршруте дважды.

Пример

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

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

a1
b3
d2
b1

a1
h8

a1
c2
e3
g2
h4
g6
h8

Решение

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

struct coord
	{
		int x,y;
	};
const int n=8;
int main()
	{
		int chessboard[n][n];
		bool k;
		string s0,s1;
		int step=0;
		coord start, finish;
		cin>>s0>>s1;
		start.x=(int)s0[0]-97;
		start.y=s0[1]-49;
		finish.x=(int)s1[0]-97;
		finish.y=s1[1]-49;
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				chessboard[i][j]=-1;
		chessboard[start.x][start.y]=0;
		k=true;
		while(chessboard[finish.x][finish.y]==-1)
			{
				k=false;
				for(int i=0;i<n;i++)
					for(int j=0;j<n;j++)
						if(chessboard[i][j]==step)
							{
								for(int a=fmax(0,i-2);a<=fmin(n-1,i+2);a++)
									for(int b=fmax(0,j-2);b<=fmin(n-1,j+2);b++)
										if((chessboard[a][b]==-1)&&(((abs(i-a)==2)&&(abs(j-b)==1))||((abs(i-a)==1)&&(abs(j-b)==2))))
											{
              									chessboard[a][b]=step+1;
              									k=true;
											}
							}
					if(!k) chessboard[finish.x][finish.y]=0;
					else step++;
			}
		if (chessboard[finish.x][finish.y]==0) cout<<"start=finish"<<endl;
		else
			{
				coord path[8];
				path[0].x=finish.x;
				path[0].y=finish.y;
				for(int i=0;i<step;i++)
					{
						int x=path[i].x;
						int y=path[i].y;
						for(int a=fmax(0,x-2);a<=fmin(n-1,x+2);a++)
							for(int b=fmax(0,y-2);b<=fmin(n-1,y+2);b++)
								if((chessboard[a][b]==chessboard[x][y]-1)&&(((abs(x-a)==2)&&(abs(y-b)==1))||((abs(x-a)==1)&&(abs(y-b)==2))))
									{
										path[i+1].x=a;
										path[i+1].y=b;
									}
					}
				for(int i=step;i>=0;i--)
				cout<<(char)(path[i].x+97)<<path[i].y+1<<endl;
			}
		return 0;
	}

#include <iostream>

#include <math.h>

using namespace std;

struct coord

{

int x,y;

};

const int n=8;

int main()

{

int chessboard[n][n];

bool k;

string s0,s1;

int step=0;

coord start, finish;

cin>>s0>>s1;

start.x=(int)s0[0]-97;

start.y=s0[1]-49;

finish.x=(int)s1[0]-97;

finish.y=s1[1]-49;

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

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

chessboard[i][j]=-1;

chessboard[start.x][start.y]=0;

k=true;

while(chessboard[finish.x][finish.y]==-1)

{

k=false;

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

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

if(chessboard[i][j]==step)

{

for(int a=fmax(0,i-2);a<=fmin(n-1,i+2);a++)

for(int b=fmax(0,j-2);b<=fmin(n-1,j+2);b++)

if((chessboard[a][b]==-1)&&(((abs(i-a)==2)&&(abs(j-b)==1))||((abs(i-a)==1)&&(abs(j-b)==2))))

{

chessboard[a][b]=step+1;

k=true;

}

if(!k) chessboard[finish.x][finish.y]=0;

else step++;

}

if (chessboard[finish.x][finish.y]==0) cout<<"start=finish"<<endl;

else

{

coord path[8];

path[0].x=finish.x;

path[0].y=finish.y;

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

{

int x=path[i].x;

int y=path[i].y;

for(int a=fmax(0,x-2);a<=fmin(n-1,x+2);a++)

for(int b=fmax(0,y-2);b<=fmin(n-1,y+2);b++)

if((chessboard[a][b]==chessboard[x][y]-1)&&(((abs(x-a)==2)&&(abs(y-b)==1))||((abs(x-a)==1)&&(abs(y-b)==2))))

{

path[i+1].x=a;

path[i+1].y=b;

}

for(int i=step;i>=0;i--)

cout<<(char)(path[i].x+97)<<path[i].y+1<<endl;

}

return 0;

}

Читаем входные данные. Преобразуем их в координаты начального и финального поля на шахматной доске. Массив chessboard сначала заполняем -1 (не пройденные поля), затем значение в поле с начальными координатами присваиваем 0. Затем будем отмечать все доступные ходы коня до тех пор пока не изменится значение в финальном поле. Затем, если у нас не совпали начальное и финальное поле будем восстанавливать путь коня. Создаем массив в котором и будет путь коня. Первое значение которое мы заносим в массив будет наше финальное поле. Затем с этого поля будем рассматривать все возможные ходы которые пройдут по уже помеченным клеткам. Если в финальное поле можно было попасть несколькими путями одинаковой длины то нам не имеет значение каким из них возвращаться в начальное поле. Затем выводим массив пути в обратном порядке.

Код на ideone.

Ковальський Олександр Дмитрович

А702а

24/06/2015 by Куленюк Денис Віталійович

Дана квадратная матрица порядка [latex]n[/latex].
Получить вектор [latex]Ab[/latex], где [latex]b[/latex]-вектор, элементы которого вычисляются по формуле: [latex]{b}_{i}={\frac{1}{{i}^{2}+2}}[/latex], где [latex]i=1,2,\dots,n[/latex].

1	2
3	4

0.666667

1.66667

Пройдено

5	6
7	8

2.66667

3.66667

Пройдено

При рассмотрении ряда квадратов чисел [latex](1, 4 , 9, \dots)[/latex], заметно, что числа следующей степени увеличиваются на четные числа, при этом модификатор предыдущего элемента на [latex]2[/latex] меньше чем следующего.
Все что нам остается сделать, это добавить генерацию вектора [latex]b[/latex], через модифицирующий элемент (преимущества которого состоят в частности, в том, что мы намного ускоряем вычисления квадратов, используя уже имеющиеся нас данные), в первый цикл (цикл ввода матрицы [latex]a[/latex]), а во втором цикле уже организовать вывод и вычисление собственно результирующего вектора.

Код программы: http://ideone.com/bl2iJE.

#include <cstdlib>
#include <iostream>

using namespace std;

int main(){
	int n;
	cin >> n;
	double a[n][n], b[n], res[n];
	int modif = 1;						// переменная ускоряющая поиск квадрата i
	int y = 0;
	for( int i=0 ; i<n ; i++, modif+=2 ){			// 
		res[i] = 0;
		y += modif;											// модифицируем переменную возведения в тепень
		b[i] = 1.0/(y+2);										// генерируем b[i]
		for( int j=0 ; j<n ; j++ ){			// 
			cin >> a[i][j];
		}
	}

	for( int i=0 ; i<n ; i++ ){			// задает A
		for( int j=0 ; j<n ; j++ ){			// задает смещение суммы
			res[i] += a[i][j]*b[j];
		}
		cout << res[i] << (i+1 == n ? '\n' : ' ');
	}
}

#include <cstdlib>

#include <iostream>

using namespace std;

int main(){

int n;

cin >> n;

double a[n][n], b[n], res[n];

int modif = 1; // переменная ускоряющая поиск квадрата i

int y = 0;

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

res[i] = 0;

y += modif; // модифицируем переменную возведения в тепень

b[i] = 1.0/(y+2); // генерируем b[i]

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

cin >> a[i][j];

}

for( int i=0 ; i<n ; i++ ){ // задает A

for( int j=0 ; j<n ; j++ ){ // задает смещение суммы

res[i] += a[i][j]*b[j];

}

cout << res[i] << (i+1 == n ? '\n' : ' ');

}

Куленюк Денис Віталійович

А407

26/11/2014 by Бронфен-Бова Роман

Задача:
Даны натуральные числа n и m, действительное число r, действительная матрица размера nxm. Получить значение [latex]{b}_{1}{r}^{n-1}+{b}_{2}{r}^{n-2}+\dots+{b}_{n}[/latex], где [latex]{b}_{k}[/latex] — первый по порядку положительный элемент в k-й строке матрицы [latex](k=1,\dots,n)[/latex]; если в k-строке нет положительных элементов, то [latex]{b}_{k}=0.5[/latex].

Тесты:

nxm	r	Матрица	Результат	Комментарий
2х2	2.5	[latex]\begin{pmatrix} -1 & 1 \\ 1 & 0 \end{pmatrix}[/latex]	3.5	Пройдено
3×4	3.14	[latex]\begin{pmatrix}5.7 & 6.7 & -7.7 & 0.9\\-3.0 & 2.3 & -5.0 & -2.4\\6.7 & 3.5 & 0.0 & 4.4\end{pmatrix}[/latex]	70.1	Пройдено
2×4	2.71	[latex]\begin{pmatrix}-9.0 &-8.8 &-7.3 & 7.5\\-6.3 &-9.7 & 6.8 &-0.5\end{pmatrix}[/latex]	27.1	Пройдено

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

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

int main() {
	int n,m; scanf("%d %d",&n,&m);
	double r; scanf("%lf",&r);
	double a[n][m];
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			scanf("%lf", &a[i][j]);
	double sum = 0;
	for(int i = 0; i < n; i++) {
		double b = 0.5;
		for(int j = 0; j < m; j++)
			if(a[i][j]>0) {
				b = a[i][j];
				break;
			}
		sum += b*pow(r,n-i-1);
	}
	printf("%lf",sum);
	return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

int main() {

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

double r; scanf("%lf",&r);

double a[n][m];

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

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

scanf("%lf", &a[i][j]);

double sum = 0;

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

double b = 0.5;

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

if(a[i][j]>0) {

b = a[i][j];

break;

}

sum += b*pow(r,n-i-1);

}

printf("%lf",sum);

return 0;

}

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

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

class Main
{
	static Scanner sc = new Scanner(System.in);
	
	public static void main (String[] args) throws java.lang.Exception
	{
		int n, m;
		n = sc.nextInt();
		m = sc.nextInt();
		double r = sc.nextDouble();
		double[][] a = new double[n][m];
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				a[i][j] = sc.nextDouble();
			}
		}
		double sum = 0;
		for(int i = 0; i < n; i++){
			double b = 0.5;
			for(int j = 0; j < m; j++){
				if(a[i][j] > 0){
					b = a[i][j];
					break;
				}
			}
			sum += b*Math.pow(r, n-i-1);
		}
		System.out.println(sum);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

static Scanner sc = new Scanner(System.in);

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

{

int n, m;

n = sc.nextInt();

m = sc.nextInt();

double r = sc.nextDouble();

double[][] a = new double[n][m];

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

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

a[i][j] = sc.nextDouble();

}

double sum = 0;

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

double b = 0.5;

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

if(a[i][j] > 0){

b = a[i][j];

break;

}

sum += b*Math.pow(r, n-i-1);

}

System.out.println(sum);

}

Идея решения:
Считать n, m как целочисленные переменные. После этого считать r как переменную типа double. Следующим считать массив nxm созданный благодаря генератору матриц из случайных чисел заданного размера. Завести переменную [latex]sum = 0[/latex] для хранения результата. Проверять построчно каждый столбик на наличие положительного числа и прибавить первое положительное число в строке, умноженное на [latex]{r}^{n-i-1}[/latex], к результаты. В случает отсутствия положительного элемента в строке, брать 0.5. В конце вывести результат.

Бронфен-Бова Роман

Ю4.32

13/11/2014 by Григорян Артак

Суммы по косой. Просуммировать элементы матрицы [latex]A(n,n)[/latex] по каждой из линий , параллельных главной диагонали. Напечатать полученные суммы.

Матрица	Суммы
1 2 3 4 5 6 7 8 9	7 12 15 8 3
-1 2 -3 4 10 5 11 6 -7 8 -9 2 12 5 13 6	12 -2 31 1 15 3 4
0 0 0 0	0 0 0

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

#include <iostream>
using namespace std;

int main() 
{
	int t;
	cin>>t;
	const int n=t;
	int a[n][n];
	int b[2*n-1];
	for (int i=0;i<2*n-1;i++)
		b[i]=0;
	for (int i=0;i<n;i++)
	{
		for (int j=0;j<n;j++)
			{
				cin>>a[i][j];
				cout<<a[i][j]<<" ";
			}
		cout<<"\n";
	}
	for (int i=0;i<n;i++)
		for (int j=0;j<n;j++)
			{
				b[i-j+n-1]+=a[i][j];
			}
	for (int i=2*n-2;i>=0;i--)
		cout<<b[i]<<" ";
	
	return 0;
}

#include <iostream>

using namespace std;

int main()

{

int t;

cin>>t;

const int n=t;

int a[n][n];

int b[2*n-1];

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

b[i]=0;

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

{

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

{

cin>>a[i][j];

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

}

cout<<"\n";

}

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

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

{

b[i-j+n-1]+=a[i][j];

}

for (int i=2*n-2;i>=0;i--)

cout<<b[i]<<" ";

return 0;

}

Сначала вводим размер квадратной матрицы — [latex]n[/latex]. Создаем одномерный массив [latex]b[/latex] в который будет результат. В нем будет [latex]2n-1[/latex] элементов, которые мы заполняем нулями.После чего в цикле будем накапливать суммы [latex]b[i-j+n-1]+=a[i][j].[/latex].

При  [latex]i=j[/latex], мы записываем сумму диагоналей в  [latex]b[n-1][/latex], который находиться в середине нашего массива  [latex]b[/latex], как нам и нужно.
Если  [latex]i>j[/latex], мы записываем суммы в элементы после середины нашего массива [latex]b[/latex].
Если  [latex]i<j[/latex], мы записываем суммы в элементы до середины нашего массива [latex]b[/latex].
Константу, которая нам нужна, будем искать по формуле [latex] max(j) — min(i)[/latex], которая равна [latex]n-1[/latex].

Код программы можно посмотреть тут

Григорян Артак

А401

10/11/2014 by Ілларіонова Марія Валеріївна

Дана действительная квадратная матрица порядка [latex]n[/latex], натуральные числа [latex]i, j \left(1\leq i\leq n, 1\leq j\leq n \right)[/latex]. Из матрицы удалить [latex]i[/latex]-строку и [latex]j[/latex]-столбец.

[latex]n[/latex]	Матрица.	[latex]i[/latex]	[latex]j[/latex]	Полученная матрица.	Комментарий.
3	1 2 3 4 5 6 7 8 9	2	1	2 3 8 9	Тест пройден.
4	0,5 1 6 0 3 8 12 0,3 10 4,6 8 9 0 3,5 6,4 10	4	3	0,5 1 0 3 8 0,3 10 4,6 9	Тест пройден.
2	-40 87 9 -3	1	1	-3	Тест пройден.

Код программы (C++):

#include <iostream>
using namespace std;
 
int main() {
	int n;
	cin >> n;
	double **m;
	m=new double *[n];
	for (int i=0; i<n; i++)	m[i]=new double [n];
	double **m1;
	m1=new double *[n-1];
	for (int i=0; i<n-1; i++)	m1[i]=new double [n-1];
	for (int i=0; i<n; i++) {
		for (int j=0; j<n; j++) {
			cin >> m[i][j];
		}
	}
	int i0, j0;
	cin >> i0 >> j0;
	for (int i=0, tr=0; tr<n-1;) {
		if (i!=i0-1) {
			for (int j=0, td=0; td<n-1; j++, td++) {
				if (j==j0-1) j++;
				m1[tr][td]=m[i][j];
			}
			i++;
			tr++;
		}
		else i++;
	}
	delete []m;
	m=m1;
	for (int i=0; i<n-1; i++) {
		for (int j=0; j<n-1; j++) {
			printf ("%5.3lf\t", m[i][j]);
		}
		cout << endl;
	}
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

double **m;

m=new double *[n];

for (int i=0; i<n; i++) m[i]=new double [n];

double **m1;

m1=new double *[n-1];

for (int i=0; i<n-1; i++) m1[i]=new double [n-1];

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

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

cin >> m[i][j];

}

int i0, j0;

cin >> i0 >> j0;

for (int i=0, tr=0; tr<n-1;) {

if (i!=i0-1) {

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

if (j==j0-1) j++;

m1[tr][td]=m[i][j];

}

i++;

tr++;

}

else i++;

}

delete []m;

m=m1;

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

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

printf ("%5.3lf\t", m[i][j]);

}

cout << endl;

}

return 0;

}

Java:

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

class Ideone {
	public static void main (String[] args) {
		Scanner in = new Scanner (System.in);
		int n;
		n = in.nextInt();
		double [][]m = new double[n][n];
		double [][]m1 = new double[n-1][n-1];
		for (int i=0; i<n; i++) {
			for (int j=0; j<n; j++) {
				m[i][j] = in.nextDouble();
			}
		}
		int i0, j0;
		i0 = in.nextInt();
		j0 = in.nextInt();
		for (int i=0, tr=0; tr<n-1;) {
			if (i!=i0-1) {
				for (int j=0, td=0; td<n-1; j++, td++) {
					if (j==j0-1) j++;
					m1[tr][td]=m[i][j];
				}
				i++;
				tr++;
			}
			else i++;
		}
		m=m1;
		for (int i=0; i<n-1; i++) {
			for (int j=0; j<n-1; j++) {
				System.out.print(m[i][j]+"    ");
			}
			System.out.println();
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone {

public static void main (String[] args) {

Scanner in = new Scanner (System.in);

int n;

n = in.nextInt();

double [][]m = new double[n][n];

double [][]m1 = new double[n-1][n-1];

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

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

m[i][j] = in.nextDouble();

}

int i0, j0;

i0 = in.nextInt();

j0 = in.nextInt();

for (int i=0, tr=0; tr<n-1;) {

if (i!=i0-1) {

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

if (j==j0-1) j++;

m1[tr][td]=m[i][j];

}

i++;

tr++;

}

else i++;

}

m=m1;

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

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

System.out.print(m[i][j]+" ");

}

System.out.println();

}

Сначала пользователю предлагается ввести порядок матрицы, затем элементы этой матрицы. После чего, по условию задачи, пользователь должен задать [latex]i[/latex]-строку и [latex]j[/latex]-столбец, которые программа должна изъять из матрицы.

Протестировать программу можно здесь (C++) и здесь (Java).

Ілларіонова Марія Валеріївна

Ю4.27

20/10/2014 by Ілларіонова Марія Валеріївна

Задача Ю4.27. Сессия. Результаты сессии, состоящей из трёх экзаменов, для группы из [latex]n[/latex] студентов представлены матрицей [latex]K \left(n,3 \right)[/latex]. Оценка ставится по четырёхбалльной системе; неявка обозначена единицей. Подсчитать количество неявок, неудовлетворительных, удовлетворительных, хороших и отличных оценок по каждому экзамену.

[latex]n[/latex]	Оценки.	Результат.	Комментарий.
3	5 3 1 4 3 5 5 2 3	1: неявка (1), уд (1), отл (1). 2: уд (1), хор (1), отл (1). 3: неуд (1), уд (1), отл (1).	Тест пройден.
6	5 4 2 1 1 3 3 2 1 4 4 2 5 5 3 4 2 1	1: неявка (2), неуд (1), уд (1), хор (1), отл (1). 2: неявка (1), неуд (2), уд (1), хор (2). 3: неявка (1), неуд (1), уд (1), хор (1), отл (2).	Тест пройден.
2	2 4 1 5 3 3	1: неуд (1), хор (1). 2: неявка (1), отл (1). 3: уд (2).	Тест пройден.

Код программы (C++):

#include <iostream>
using namespace std;

int main() {
	int n;
	cin >> n;
	int K[n][3];
	int o[5][3]={};
	for (int j=0; j<3; j++) {
		for (int i=0; i<n; i++) {
			cin >> K[i][j];
			o[K[i][j]-1][j]+=1;
		}
	printf ("Результаты %d-го экзамена: %d - неявок, %d - неудовлетворительно, %d - удовлетворительно, %d - хорошо, %d - отлично.\n", j+1, o[0][j], o[1][j], o[2][j], o[3][j], o[4][j]);
	}
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

int K[n][3];

int o[5][3]={};

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

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

cin >> K[i][j];

o[K[i][j]-1][j]+=1;

}

printf ("Результаты %d-го экзамена: %d - неявок, %d - неудовлетворительно, %d - удовлетворительно, %d - хорошо, %d - отлично.\n", j+1, o[0][j], o[1][j], o[2][j], o[3][j], o[4][j]);

}

return 0;

}

Java:

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int n;
		Scanner in = new Scanner (System.in);
		n=in.nextInt();
		int [][] K = new int[n][3];
		int [][] o = new int [5][3];
		for (int j=0; j<3; j++) {
			for (int i=0; i<n; i++) {
				K[i][j]=in.nextInt();
				o[K[i][j]-1][j]++;
			}
		System.out.format ("Результаты %d-го экзамена: %d - неявок, %d - неудовлетворительно, %d - удовлетворительно, %d - хорошо, %d - отлично.%n", j+1, o[0][j], o[1][j], o[2][j], o[3][j], o[4][j]);
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

int n;

Scanner in = new Scanner (System.in);

n=in.nextInt();

int [][] K = new int[n][3];

int [][] o = new int [5][3];

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

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

K[i][j]=in.nextInt();

o[K[i][j]-1][j]++;

}

System.out.format ("Результаты %d-го экзамена: %d - неявок, %d - неудовлетворительно, %d - удовлетворительно, %d - хорошо, %d - отлично.%n", j+1, o[0][j], o[1][j], o[2][j], o[3][j], o[4][j]);

}

Изначально пользователю предлагается ввести количество студентов [latex]n[/latex]. Затем создаётся массив [latex]K \left(n,3\right)[/latex], в котором будут храниться оценки студентов, а так же двумерный массив [latex]o \left(5,3 \right)[/latex], который, собственно говоря, и будет хранить статистику по оценкам. Внешний цикл перебирает экзамены (по [latex]j[/latex]), а внутренний — студентов (по [latex]i[/latex]). Затем пользователю предлагается ввести оценки студентов (сначала вводятся все оценки за первый экзамен, затем за второй, а потом уж за третий). В этом цикле находится «счётчик», который подсчитывает количество определённых оценок (или неявок) в зависимости от массива [latex]K \left(n,3\right)[/latex] на данном этапе цикла. Затем на экран выводятся элементы массива (в дальнейшем все элементы сохранятся, то есть с оценками студентов можно будет работать и дальше).

Код программы можно посмотреть тут (C++) и тут (Java).

Ілларіонова Марія Валеріївна

Skynet: the Virus

14/10/2014 by Бронфен-Бова Роман

SKYNET FINALE — LEVEL 1

Los Angeles 2029 — Resistance HQ — Review of facts:

В минувшую субботу, сотни отважных бойцов рисковали своей жизнью, чтобы уничтожить Skynet. СТОП

Используя зараженных мото-терминаторов, им удалось привить смертельный вирус к Skynet. СТОП

Проблема: Skynet борется. СТОП

Джон, ещё раз, нам нужна ваша помощь. СТОП

Задача:

У нас в распоряжении целый граф узлов. Некоторые из них названы шлюзами. Шлюзы надо защищать от злобного Skynet агента, который способен передвигаться по связям между узлами. Способ защиты очень прост: каждый ход можно навсегда заблокировать одну связь, тем самым, через некоторое количество ходов, полностью закрыть шлюз от нежелательных гостей.

Первичная инициализация:

Первая строка: 3 целых числа N L E

N — Количество узлов, включая шлюзы
L — Количество связей
E — Количество шлюзов

Следующие L строк: по два числа на строку (N1, N2), означающие, что между узлами с индексами N1 и N2 присутствует связь.
Следующие E строк: по одному числу на строку, означающие индексы шлюзов.

Инициализация за каждый игровой тик:

Одно число — индекс связи, на которой находится Skynet агент.

Вывод за каждый игровой тик:

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

Программа:

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

using namespace std;

int main()
{
    int N; //Количество узлов, включая шлюзы
    int L; //Количество связей
    int E; //Количество шлюзов
    cin >> N >> L >> E; cin.ignore();
    
    int N1[L][2]; // Массив для связей
    for (int i = 0; i < L; i++) {
        cin >> N1[i][0] >> N1[i][1]; cin.ignore();
    }
    
    int EI[E]; // Индексы шлюзов
    for (int i = 0; i < E; i++) {
        cin >> EI[i]; cin.ignore();
    }
    
    // Алгоритм сортировки (его достаточно)
    for(int i = 0; i < L; i++){
        for(int k =0; k < E; k++){
            if(N1[i][1] == EI[k]) swap(N1[i][1],N1[i][0]);
        }
    }

    // игровой цикл
    while (1) {
        int SI; //Индекс связи, на которой находится Агент
        cin >> SI; cin.ignore();

        bool AgentIsNear = false; //Агент возле шлюза!
        
        for(int i = 0; i < L; i++){
            bool T = false; //Для прерывания цикла
            for(int k = 0; k < E; k++){
                if(EI[k] == N1[i][0] && SI == N1[i][1]){
                    cout << EI[k] << ' ' << SI << endl;
                    N1[i][0] = -1;
                    AgentIsNear = true;
                    T = true;
                    break;
                }
            }
            if(T) break;
        }
        
        if(!AgentIsNear){
            for(int i = 0; i < L; i++){
                bool T = false; //Для прерывания цикла
                for(int k = 0; k < E; k++){
                    if(N1[i][0] == EI[k]){
                        cout << EI[k] << ' ' << N1[i][1] << endl;
                        N1[i][0] = -1;
                        T = true;
                        break;
                    }
                }
                if(T) break;
            }
        }
        
    }
}

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

int main()

{

int N; //Количество узлов, включая шлюзы

int L; //Количество связей

int E; //Количество шлюзов

cin >> N >> L >> E; cin.ignore();

int N1[L][2]; // Массив для связей

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

cin >> N1[i][0] >> N1[i][1]; cin.ignore();

}

int EI[E]; // Индексы шлюзов

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

cin >> EI[i]; cin.ignore();

}

// Алгоритм сортировки (его достаточно)

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

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

if(N1[i][1] == EI[k]) swap(N1[i][1],N1[i][0]);

}

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

while (1) {

int SI; //Индекс связи, на которой находится Агент

cin >> SI; cin.ignore();

bool AgentIsNear = false; //Агент возле шлюза!

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

bool T = false; //Для прерывания цикла

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

if(EI[k] == N1[i][0] && SI == N1[i][1]){

cout << EI[k] << ' ' << SI << endl;

N1[i][0] = -1;

AgentIsNear = true;

T = true;

break;

}

if(T) break;

}

if(!AgentIsNear){

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

bool T = false; //Для прерывания цикла

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

if(N1[i][0] == EI[k]){

cout << EI[k] << ' ' << N1[i][1] << endl;

N1[i][0] = -1;

T = true;

break;

}

if(T) break;

}

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

Переходы между узлами занесены в двумерный массив N1, далее этот массив был своеобразно отсортирован (для удобства). В игровом цикле объявляем булевую переменную AgentIsNear — агент вблизи шлюза.

Первый цикл: Проверяем каждую клетку вокруг каждого шлюза на присутствие там агента. И если он таки там есть, блокируем переход, меняем первую переменную (отвечающую за шлюз) в массиве переходов (N1) на -1 (значение, которое никогда не встретится), изменяем AgentIsNear на true и прерываем цикл.

Второй цикл: так как агент гуляет где-то далеко, то мы блокируем любой свободный проход любого шлюза.

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

Программа проходит все тесты на MEDIUM и, что удивительно, половину тестов на HARD! Взято с CodinGame

Бронфен-Бова Роман