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 2812. Уголок

08/06/2018 by Георгий Мартынюк

Задача

Дана прямоугольная доска [latex]M×N[/latex], некоторые клетки в которой вырезаны. Сколькими способами можно поставить на неё «уголок» из трёх клеток так, чтобы все три клетки уголка находились внутри доски и не были вырезаны?

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

В первой строке входного файла даны два числа [latex]M[/latex] и [latex]N[/latex] [latex](1 \leq M, N \leq 100)[/latex], разделённые пробелом. В следующих [latex]M[/latex] строках содержится по [latex]N[/latex] символов в каждой; [latex]i[/latex]-ый символ [latex]j[/latex]-ой из этих строк равен ‘X’ (большая буква икс), если клетка вырезана, и ‘.’ (точка) в противном случае.

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

Выведите одно число — сколько существует способов поставить уголок на данную доску.

Тесты

Входные данные	Выходные данные
2 2 .. ..	4
2 3 ..X .X.	1
5 4 …. X.XX …. X..X ..XX	12

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

#include <iostream>
using namespace std;
 
int main() {
    int x, y;
    cin >> x >> y;
    bool **mas = new bool*[x];
    for (int i = 0; i < x; ++i){
        mas[i] = new bool[y];
    }
    for (int i = 0; i < x; ++i){
        for (int j = 0; j < y; ++j){
            char buff;
            cin >> buff;
            if (buff == '.') mas[i][j] = true; 
            else mas[i][j] = false;
        }
        cout << endl;
    }
    int sum = 0;
    for (int i = 0; i < x; ++i){
        for (int j = 0; j < y; ++j){
            if (mas[i][j]){
                if (i - 1 >= 0 && j - 1 >= 0) if (mas[i - 1][j] && mas[i][j - 1])  ++sum;
                if (i - 1 >= 0 && j + 1 < y) if (mas[i - 1][j] && mas[i][j + 1])  ++sum; 
                if (i + 1 < x && j + 1 < y) if (mas[i + 1][j] && mas[i][j + 1])  ++sum; 
                if (i + 1 < x && j - 1 >= 0) if (mas[i + 1][j] && mas[i][j - 1])  ++sum; 
            }
        }
    }
    cout << sum;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int x, y;

cin >> x >> y;

bool **mas = new bool*[x];

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

mas[i] = new bool[y];

}

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

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

char buff;

cin >> buff;

if (buff == '.') mas[i][j] = true;

else mas[i][j] = false;

}

cout << endl;

}

int sum = 0;

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

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

if (mas[i][j]){

if (i - 1 >= 0 && j - 1 >= 0) if (mas[i - 1][j] && mas[i][j - 1]) ++sum;

if (i - 1 >= 0 && j + 1 < y) if (mas[i - 1][j] && mas[i][j + 1]) ++sum;

if (i + 1 < x && j + 1 < y) if (mas[i + 1][j] && mas[i][j + 1]) ++sum;

if (i + 1 < x && j - 1 >= 0) if (mas[i + 1][j] && mas[i][j - 1]) ++sum;

}

cout << sum;

return 0;

}

Решение

Для решения данной задачи создаем динамический массив типа bool x на y. Заполняем соответствующий элемент значением true, когда вводится «.» и значением false в противном случае. Далее увеличиваем значение количества уголков на $1$, если существуют не пустые клетки.

Ссылки

e-olymp
Ideone

Related Images:

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

05/06/2018 by Костя Григорян

Задача

Заполнить массив размера $n × n$ единичками по спирали (см. пример).

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

Одно нечетное натуральное число $n$, не превышающее $50$.

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

Вывести построенную спираль. Центральная клетка должна содержать $0$.

Тесты

Входные данные	Выходные данные
[latex]7[/latex]	[latex]1111111 \\ 0000001 \\ 1111101 \\ 1000101 \\ 1011101 \\ 1000001 \\ 1111111[/latex]
[latex]1[/latex]	[latex]0[/latex]
[latex]3[/latex]	[latex]111 \\ 001 \\ 111[/latex]
[latex]5[/latex]	[latex]11111 \\ 00001 \\ 11001 \\ 10001 \\ 11111[/latex]

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

#include <iostream>
using namespace std;

bool s[50][50];

int main() {
    int n;
    cin >> n;
    for(int i=0; i<n; i++)
    {
        s[0][i]=1;
        s[n-1][i]=1;
        s[i][n-1]=1;
    }
    int h=n-2, d=n-2;
    int pointx=n-1, pointy=0; 
    while(1)
    {
        for(int i=0; i<h; i++)
        {
            s[pointx-i][pointy]=1;
        }
        pointx-=h-1;
        h-=2;
        if(h<=0)
            break;
        for(int i=0; i<d; i++)
        {
            s[pointx][pointy+i]=1;
        }
        pointy+=d-1;
        d-=2;
        if(d<=0)
            break;
            for(int i=0; i<h; i++)
        {
            s[pointx+i][pointy]=1;
        }
        pointx+=h-1;
        h-=2;
        if(h<=0)
            break;
        for(int i=0; i<d; i++)
        {
            s[pointx][pointy-i]=1;
        }
        pointy-=d-1;
        d-=2;
        if(d<=0)
            break;
    }
    s[n/2][n/2]=0;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            cout << s[i][j];
        }
        cout << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

bool s[50][50];

int main() {

int n;

cin >> n;

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

{

s[0][i]=1;

s[n-1][i]=1;

s[i][n-1]=1;

}

int h=n-2, d=n-2;

int pointx=n-1, pointy=0;

while(1)

{

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

{

s[pointx-i][pointy]=1;

}

pointx-=h-1;

h-=2;

if(h<=0)

break;

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

{

s[pointx][pointy+i]=1;

}

pointy+=d-1;

d-=2;

if(d<=0)

break;

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

{

s[pointx+i][pointy]=1;

}

pointx+=h-1;

h-=2;

if(h<=0)

break;

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

{

s[pointx][pointy-i]=1;

}

pointy-=d-1;

d-=2;

if(d<=0)

break;

}

s[n/2][n/2]=0;

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

{

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

{

cout << s[i][j];

}

cout << endl;

}

return 0;

}

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

Для начала мы верхнюю, нижнюю и правую грани зразу заполним единицами. Далее идем поочередно в четырех направления (вверх, вправо, вниз, влево). Мы имеем два параметра: ширину и высоту заполняемого единицами отрезка (ширине соответствуют движения вправо и влево, высоте — вверх и вниз). На каждом шаге уменьшаем соответствующий заполняемый отрезок (ширину или высоту) на $2$ и проверяем, чтобы он был больше $0$, иначе заканчиваем. На протяжении всего решения храним еще два параметра: координаты точки, откуда начнем следующий шаг.
P.s. На сайте www.e-olymp.com это решение не проходит полностью из-за неправильности $5$-го теста. У них в $5$-ом тесте центральный элемент $1$, что противоречит условию.

Ссылки

Условие задачи на e-olymp
Код решения

Related Images:

e-olymp 4557. Одинокий король

13/05/2018 by Андрей Лисовой

Задача

Одинокий король долго бродил по бесконечной шахматной доске. Известна последовательность из [latex]n[/latex] его ходов (вверх, вниз, влево, вправо, вверх-влево и т.п.) — возможные ходы короля показаны на рисунке снизу.

Определите, побывал ли король дважды на одном и том же поле за свои [latex]n[/latex] ходов.

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

В первой строке задано общее число ходов короля [latex]n[/latex] [latex](0 ≤ n ≤ 1000)[/latex]. В последующих [latex]n[/latex] строках заданы направления перемещения короля: строка под номером [latex]i + 1[/latex] задаёт направление перемещения короля на [latex]i[/latex]-ом ходу.

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

Выведите единственное число — номер хода, на котором король впервые попал на какую-то клетку во второй раз. Если же такое событие не произошло, то в первой строке выведите сообщение «Ok» (без кавычек), а во второй — манхэттенское расстояние между начальной и конечной точками путешествия одинокого короля.

Напоминаем, что манхэттенское расстояние между точками с координатами [latex](x_1, y_1)[/latex] и [latex](x_2, y_2)[/latex] определяется по формуле: [latex]d = |x_2 — x_1| + |y_2 — y_1|[/latex].

Тесты

Входные данные	Выходные данные
[latex]5[/latex] [latex]1[/latex] [latex]2[/latex] [latex]4[/latex] [latex]7[/latex] [latex]4[/latex]	[latex]4[/latex]
[latex]5[/latex] [latex]1[/latex] [latex]2[/latex] [latex]4[/latex] [latex]6[/latex] [latex]4[/latex]	[latex]Ok[/latex] [latex]2[/latex]
[latex]8[/latex] [latex]3[/latex] [latex]3[/latex] [latex]7[/latex] [latex]7[/latex] [latex]5[/latex] [latex]5[/latex] [latex]3[/latex] [latex]3[/latex]	[latex]3[/latex]
[latex]7[/latex] [latex]2[/latex] [latex]4[/latex] [latex]2[/latex] [latex]8[/latex] [latex]8[/latex] [latex]1[/latex] [latex]5[/latex]	[latex]Ok[/latex] [latex]3[/latex]
[latex]12[/latex] [latex]2[/latex] [latex]3[/latex] [latex]4[/latex] [latex]1[/latex] [latex]3[/latex] [latex]2[/latex] [latex]5[/latex] [latex]6[/latex] [latex]8[/latex] [latex]2[/latex] [latex]1[/latex] [latex]7[/latex]	[latex]10[/latex]

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

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

int x[2001][2001];

int main() {
    int n;
    cin>>n;
    int move;
    int xPos=1001, yPos=1001;
    for(int i=0; i<n; i++) {
        cin>>move;
        if(x[xPos][yPos]==1) { 
            cout<<i;
            return 0;
        }
        else x[xPos][yPos]=1;
        if(move==1) {
            xPos--;
            yPos++;
        }
        if(move==2) {
            yPos++;
        }
        if(move==3) {
            xPos++;
            yPos++;
        }
        if(move==4) {
            xPos++;
        }
        if(move==5) {
            xPos++;
            yPos--;
        }
        if(move==6) {
            yPos--;
        }
        if(move==7) {
            xPos--;
            yPos--;
        }
        if(move==8) {
            xPos--;
        }
    }
    cout<<"Ok"<<endl<<abs(xPos-1001)+abs(yPos-1001);
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int x[2001][2001];

int main() {

int n;

cin>>n;

int move;

int xPos=1001, yPos=1001;

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

cin>>move;

if(x[xPos][yPos]==1) {

cout<<i;

return 0;

}

else x[xPos][yPos]=1;

if(move==1) {

xPos--;

yPos++;

}

if(move==2) {

yPos++;

}

if(move==3) {

xPos++;

yPos++;

}

if(move==4) {

xPos++;

}

if(move==5) {

xPos++;

yPos--;

}

if(move==6) {

yPos--;

}

if(move==7) {

xPos--;

yPos--;

}

if(move==8) {

xPos--;

}

cout<<"Ok"<<endl<<abs(xPos-1001)+abs(yPos-1001);

return 0;

}

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

Создаем глобальный массив(изначально заполненный нулями). Задаем координаты короля по центру int xPos=1001, yPos=1001;. Затем в цикле вводим все ходы короля и проверяем был ли он уже в этой ячейке, если нет — ставим [latex]1[/latex], и вводим ход короля и задаем ему новые координаты, если да — выводим номер хода и завершаем программу. Если король ни разу не попал на ячейку, в которой уже был, то программа находим манхэттенское расстояние между начальными координатами и конечными. Задача решена.

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com

Related Images:

e-olymp 396. Дождь

15/04/2018 by Мороз Дима

Задача

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

Как это выглядит на координатной плоскости

Будем рассматривать двумерный вариант (на плоскости) этой задачи. Пусть препятствия – это наклонные непересекающиеся отрезки, а капля имеет точечные размеры. Капля падает вертикально вниз из точки, расположенной выше любого из препятствий. Если капля при падении соприкасается с отрезком-препятствием, то она стекает по отрезку вниз, пока не упадет вертикально вниз с меньшего по высоте конца отрезка.

Напишите программу, которая по координате $X$_$0$ точки появления капли над землей вычисляет координату $X$ точки соприкосновения капли с землей $(Y = 0)$.

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

Во входном файле в первой строке содержатся два целых числа через пробел – координата $X$_$0$ точки появления капли $(0 < X$_$0$ $< 10000)$ и количество отрезков-препятствий $N (0 ≤ N ≤ 100)$. Далее следует $N$ строк, каждая из которых содержит четыре разделенные пробелами числа $x$_$1$, $y$_$1$, $x$_$2$, $y$_$2$ – координаты левого и правого концов отрезка-препятствия (все числа целые и находятся в диапазоне от $0$ до $10000$, $x$_$1$ $ < x$_$2$, $y$_$1$ $≠$ $y$_$2$$)$. Отрезки не пересекаются и не соприкасаются.

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

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

Тесты

Входные данные	Выходные данные
30 4 25 35 40 30 1 32 20 30 33 22 50 29 18 10 33 19	18
12 5 12 9 13 5 17 8 19 5 13 10 10 7 6 17 4 12 13 4 5 12	13
40 3 12 30 21 39 41 5 45 70 20 30 25 35	40
70 6 45 75 598 37 489 48 726 47 673 873 46 36 60 735 373 762 483 73 364 59 462 375 583 457	726

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

#include <iostream>
using namespace std;
 
int main () 
{
    int x, n;
    cin >> x >> n;
    int N[n][4];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < 4; j++)
            cin >> N[i][j];
    for (int i = 0; i < n; i++) 
        for (int j = 0; j < n; j++) 
            for (int q = 0; q < 4; q++)
                if ((N[i][1] > N[j][1] || N[i][3] > N[j][3]) || ( (N[i][1] == N[j][1] || N[i][3] == N[j][3] ) && (N[i][0] > N[j][0] || N[i][2] > N[j][2]) ) )
                    swap(N[i][q], N[j][q]);
    for (int i = 0; i < n; i++) {
        if (x >= N[i][0] && x <= N[i][2]) 
            N[i][1] < N[i][3] ? x = N[i][0] : x = N[i][2];
        for (int j = 0; j < 4; j++)
            N[i][j] = 0;
    }
    cout << x;
 
    return 0;
}

#include <iostream>

using namespace std;

int main ()

{

int x, n;

cin >> x >> n;

int N[n][4];

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

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

cin >> N[i][j];

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

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

for (int q = 0; q < 4; q++)

if ((N[i][1] > N[j][1] || N[i][3] > N[j][3]) || ( (N[i][1] == N[j][1] || N[i][3] == N[j][3] ) && (N[i][0] > N[j][0] || N[i][2] > N[j][2]) ) )

swap(N[i][q], N[j][q]);

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

if (x >= N[i][0] && x <= N[i][2])

N[i][1] < N[i][3] ? x = N[i][0] : x = N[i][2];

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

N[i][j] = 0;

}

cout << x;

return 0;

}

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

Сортируем наш динамический массив по наибольшим координатам $y$ и, если $y$ равны, по координатам $x$.

Далее составим алгоритм решения задачи:

Если $X$ $ ∈ [x$_$1$$, x$_$2$$]$, то наша капля пересечется с данной прямой. В противном случае мы просто игнорируем данное препятствие.
Тогда мы сравниваем координаты $y$_$1$ и $y$_$2$, выбираем из них наименьшее и присваиваем соответствующую координату $x$_$1$ или $x$_$2$ координате нашей капли $X$.
Повторяем до тех пор, пока не будут обработаны все препятствия и выводим последнюю присвоенную координату $X$ нашей капли, так как она и будет координатой $x$ соприкосновения капли с зимой.

Ссылки

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

Related Images:

e-olymp 1489. Шоколад

13/04/2018 by Илья Черноморец

Задача

Петя очень любит шоколад. И Маша очень любит шоколад. Недавно Петя купил шоколадку и теперь хочет поделиться ею с Машей. Шоколадка представляет собой прямоугольник $n \cdot m$, который полностью состоит из маленьких шоколадных долек — прямоугольников $2 \cdot 1$.

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

Помогите Пете поделиться шоколадкой с Машей.

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

В первой строке входного файла два целых числа $n$ и $m$ ($1 \le n, m \le 20$, хотя бы одно из чисел $n$ и $m$ — четно). Далее следуют $n$ строк по $m$ чисел в каждой — номера долек, в которые входят соответствующие кусочки шоколадки. Дольки имеют номера от $1$ до $\frac{n \cdot m}{2}$, и никакие две дольки не имеют одинаковые номера.

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

В выходной файл выведите «$Yes$», если Петя может разломать шоколадку, не повредив дольки. Иначе выведите «$No$».

TESTS

Входные данные	Выходные данные
2 3 1 1 2 3 3 2	Yes
5 6 1 2 2 3 3 4 1 5 6 7 7 4 8 5 6 9 10 10 8 11 11 9 12 13 14 14 15 15 12 13	No
4 7 1 1 2 5 8 11 6 2 14 4 7 3 9 5 3 7 10 6 13 2 3 4 3 8 12 5 7 7	Yes

Код решения

#include <iostream>
using namespace std;


bool BreakRow (int **chocolate, int n, int m){
  for (int i = 0; i < n - 1; i++){
    bool okRow = true;
    for (int j = 0; j < m; j++){
      if(chocolate[i][j] == chocolate [i + 1][j]){okRow = false;break;}
    }
    if (okRow) return true;
  }
  return false;
}
bool BreakColumn (int **chocolate, int n, int m){
  for (int i = 0; i < m - 1; i++){
    bool okColumn = true;
    for (int j = 0; j < n; j++){
      if(chocolate[j][i] == chocolate[j][i + 1]){okColumn = false;break;}
    }
    if (okColumn) return true;
  }
  return false;
}

int check (int **chocolate, int n, int m){
  if ( BreakRow(chocolate, n, m) || BreakColumn (chocolate, n, m)) cout<<"Yes";
  else cout<<"No";
}

int main() {
  int n, m;
  cin >> n >> m;
  int **chocolate = new int* [n];
  for(int i = 0; i < n; ++i){
    chocolate[i] = new int[m];
  }
  for( int i = 0; i < n;  i++){
    for(int j = 0; j < m; j++){
      cin >> chocolate [i][j];
    }
  }
  check(chocolate, n, m);
  return 0;
}

#include <iostream>

using namespace std;

bool BreakRow (int **chocolate, int n, int m){

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

bool okRow = true;

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

if(chocolate[i][j] == chocolate [i + 1][j]){okRow = false;break;}

}

if (okRow) return true;

}

return false;

}

bool BreakColumn (int **chocolate, int n, int m){

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

bool okColumn = true;

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

if(chocolate[j][i] == chocolate[j][i + 1]){okColumn = false;break;}

}

if (okColumn) return true;

}

return false;

}

int check (int **chocolate, int n, int m){

if ( BreakRow(chocolate, n, m) || BreakColumn (chocolate, n, m)) cout<<"Yes";

else cout<<"No";

}

int main() {

int n, m;

cin >> n >> m;

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

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

chocolate[i] = new int[m];

}

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

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

cin >> chocolate [i][j];

}

check(chocolate, n, m);

return 0;

}

Решение

Для решения данной задачи нужно представить шоколадку как двухмерный массив и проверить, можно ли разломать плитку шоколада ровно, то есть одинаковое ли количество «строк» и «столбцов» шоколада. Если так, то возвращается значение true, и false в обратном случае. Для этого были созданы функции BreakRow и BreakColumn с возвращаемым значением типа bool. Затем стоит проверить возвращаемое значение. Если одна из функций принимает значение true, то выводим положительный ответ. В противном случае ответ отрицательный.

Ссылки

Условие решения на e-olymp.com
Код решения на ideone.com

Related Images:

e-olymp 5282. Седловые точки

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

Задача

Задана матрица [latex]K[/latex], содержащая [latex]n[/latex] строк и [latex]m[/latex] столбцов. Седловой точкой этой матрицы назовём элемент, который одновременно является минимумом в своей строке и максимумом в своём столбце.
Найдите количество седловых точек заданной матрицы.

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

Первая строка содержит целые числа [latex]n[/latex] и [latex]m[/latex]. [latex](1 ≤ n, m ≤ 750)[/latex]. Далее следуют [latex]n[/latex] строк по [latex]m[/latex] чисел в каждой. [latex]j[/latex]-ое число [latex]i[/latex]-ой строки равно [latex]k_{ij}[/latex]. Все [latex]k_{ij}[/latex] по модулю не превосходят [latex]1000[/latex].

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

Выведите количество седловых точек.

Тесты

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

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

#include <iostream>
#define Unknown 1001
using namespace std;

int main() {
    int n, m,uf = 0,maxi;
    //input
    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];
    //workspace
    int  max[m];
    for (int i = 0; i < m; i++){
        max[i] = Unknown;   
    }
    for (int i = 0; i < n; i++) {
        int min = x[i][0];
        for (int j = 1; j < m; j++) {
            if ( min > x[i][j] ) {
                min = x[i][j];
            }
        }
        for (int j = 0; j < m; j++) {
            if (x[i][j] == min) {
                if (max[j] != Unknown){
                    maxi = max[j];  
                }
                else {
                    maxi = x[i][j];
                    for (int l = 0; l < n; l++) {
                        if (maxi < x[l][j]){
                            maxi = x[l][j];
                        }
                    }
                    max[j] = maxi;
                }
                if ( maxi == min) {
                    uf++;
                }
            }
        }
    }
    //output
    cout << uf;
    return 0;
}

#include <iostream>

#define Unknown 1001

using namespace std;

int main() {

int n, m,uf = 0,maxi;

//input

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];

//workspace

int max[m];

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

max[i] = Unknown;

}

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

int min = x[i][0];

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

if ( min > x[i][j] ) {

min = x[i][j];

}

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

if (x[i][j] == min) {

if (max[j] != Unknown){

maxi = max[j];

}

else {

maxi = x[i][j];

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

if (maxi < x[l][j]){

maxi = x[l][j];

}

max[j] = maxi;

}

if ( maxi == min) {

uf++;

}

//output

cout << uf;

return 0;

}

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

Для каждой строки, будем осуществлять два прохода. В первом найдем минимальное число, а во втором, если значение очередного элемента будет являться в ней минимумом, то проверим будет ли оно максимумом в своем столбце таким образом, что если элемент заранее созданного массива [latex]([/latex] в котором изначально лежат все [latex]Unknown ([/latex] заранее созданная константа равная [latex]1001[/latex][latex] ([/latex] так как по условию, числа которые мы вводим не больше чем [latex]1000 ) ) )[/latex] не равен [latex]Unknown[/latex], то просто сравним элемент массива с минимумом, иначе найдем максимум для данного столбца и положим его в массив, о котором шла речь ранее и сравним уже это число с минимумом строки. Если они совпадают, то это и есть седловая точка!

Ссылки

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

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

Related Images:

e-olymp 88. Месть Ли Чака

04/02/2018 by Кирилл Волков

Задача

“Я хочу быть пиратом!” Мы напоминаем эту известную фразу Гайбраша Трипвуда из серии компьютерных игр Monkey Island («Остров Обезьян»). Гайбраш участвовал в другом приключении и серьезно нуждается в Вашей помощи, потому что на этот раз это вопрос жизни и смерти. Наш Гайбраш в последнем приключении приплыл на таинственный остров (ТО), чтобы найти подсказку для еще более таинственного сокровища. Тем временем Ли Чак узнал об этой поездке и подготовил ловушку Гайбрашу на ТО. ТО имеет прямоугольную форму (поскольку мы знаем, что он таинственный) и его карта может рассматриваться как матрица такой же размерности. Назовем каждый элемент матрицы участком. Некоторые участки могут быть заполнены горными скалами. Такие участки считаются непроходимыми.

Рассмотрим остров, карта которого изображена на рисунке. Эта карта представляет собой матрицу с $6$ строками и $7$ столбцами. Комнаты «R» показывают участки со скалами. Гайбраш должен начинать с участка, отмеченного «g», а Ли Чак – с участка «l». У Гайбраша есть шанс сбежать с этого проклятого острова, если он достигнет конечного участка, который отмечен символом «e» на карте. Каждую единицу времени Гайбраш может пойти на соседний с текущим участок по горизонтали или вертикали (но не по диагонали), если в нем нет скал, или не двигаться. То есть он может переместиться на один участок вверх, вниз, влево, вправо или вообще остаться на месте. В приведенном примере Гайбраш в первый момент времени может остаться или пойти в комнату слева от него. Все указанные правила применяются также и к движению Ли Чака, но с одним исключением: он не может войти на конечный участок (отмеченный «e»). То есть, каждую единицу времени Ли Чак может пойти на один участок вверх, вниз, влево, вправо (если только это не «R» или «e») или стоять. Мы предполагаем, что каждую единицу времени сначала делает ход (или стоит) Гайбраш, а затем ходит (или стоит) Ли Чак, в следующую единицу времени опять сначала Гайбраш, затем Ли Чак и так далее. Если Гайбраш и Ли Чак встретятся на одном участке, то Ли Чак немедленно убьет нашего бедного Гайбраша.

Ваша задача состоит в том, чтобы узнать, есть ли по крайней мере один безопасный путь или нет. Безопасный путь – это путь для Гайбраша (от «g» до «e») такой, что Ли Чак не может поймать Гайбраша на этом пути независимо от того, что он (Ли Чак) делает каждую единицу времени.

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

Первая строка входа содержит единственное целое число — количество тестовых случаев. Далее идут строки данных для тестовых случаев. Каждый тест начинается со строки, содержащей два целых числа $R$ и $C$ ($4 \leq R, C \leq 30$), которые обозначают количество строк и столбцов карты таинственного острова соответственно. Далее следуют $R$ строк, каждая содержит $C$ символов, представляющих карту. Есть единственные отметки «g», «l» и «e» на карте.

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

Для каждого теста необходимо вывести единственную строку. Если существует, по крайней мере, хотя бы один безопасный путь для тестового случая, должно быть выведено слово «YES», и слово «NO», если такого пути нет. Предполагается, что если существует безопасный путь, то необходимо не более $1000$ единиц времени для прохождения по нему Гайбраша.

Тесты

Входные данные	Выходные данные
$531$ $348$ $1645$	$911$
$1784353$ $453345$ $463973$	$214457$
$39252362$ $345673$ $786536$	$302328$
$68790234$ $679643$ $789057$	$281232$
$324$ $8564$ $45074547$	$32984424$

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

#include <iostream>
#include <vector>

using  namespace std;

const int INF = 10000000;
const string GAYBRASH = "GAYBRASH";
const string LICHACK = "LICHACK";

struct node{
    int x;
    int y;
};

vector<node> getChildrenBFS(char ** map, node parent, string hero){
    string bannedChars = "R";
    if(hero == LICHACK) bannedChars.push_back('e');
    vector<node> children;
    node leftChild = {parent.x - 1, parent.y};
    node rightChild = {parent.x + 1, parent.y};
    node downChild = {parent.x, parent.y + 1};
    node upChild = {parent.x, parent.y - 1};
    if(bannedChars.find(map[leftChild.y][leftChild.x]) == string::npos){
        children.push_back(leftChild);
    }
    if(bannedChars.find(map[rightChild.y][rightChild.x]) == string::npos){
        children.push_back(rightChild);
    }
    if(bannedChars.find(map[downChild.y][downChild.x]) == string::npos){
        children.push_back(downChild);
    }
    if(bannedChars.find(map[upChild.y][upChild.x]) == string::npos){
        children.push_back(upChild);
    }
    return children;
}

void dfsSecondPlayer(char ** map, int ** moves, string hero, node currentNode, int move){
    moves[currentNode.y][currentNode.x] = move;
    move++;
    vector<node> children = getChildrenBFS(map, currentNode, hero);
    vector<node> queue;
    for(auto e: children) {
        if (move < moves[e.y][e.x]) {
            dfsSecondPlayer(map, moves, hero, e, move);
        }
    }
}
void dfsFirstPlayer(char ** map, int ** moves, int ** secondPlayer, string hero, node currentNode, int move){
    moves[currentNode.y][currentNode.x] = move;
    move++;
    vector<node> children = getChildrenBFS(map, currentNode, hero);
    vector<node> queue;
    for(auto e: children){
        if(move < moves[e.y][e.x] && move < secondPlayer[e.y][e.x]){
            dfsFirstPlayer(map, moves, secondPlayer, hero, e, move);
        }
    }
}
int main() {
    int tests;
    cin >> tests;
    for(; tests > 0; tests--){
        int m;
        int n;
        cin >> m >> n;
        cin.ignore();
        node g;
        node l;
        node e;
        char **map = new char*[m];
        for(int i = 0; i < m; i++){
            map[i] = new char[n];
        }
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                map[i][j] = cin.get();
                switch(map[i][j]){
                    case 'g':
                        g.x = j;
                        g.y = i;
                        break;
                    case 'l':
                        l.x = j;
                        l.y = i;
                        break;
                    case 'e':
                        e.x = j;
                        e.y = i;
                        break;
                }
            }
            cin.ignore();
        }
        int **liChack = new int*[m];
        for(int i = 0; i < m; i++){
            liChack[i] = new int[n];
        }
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                liChack[i][j] = INF;
            }
        }
        dfsSecondPlayer(map, liChack, LICHACK, l, 0);
        int **gaybrash = new int*[m];
        for(int i = 0; i < m; i++){
            gaybrash[i] = new int[n];
        }
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                gaybrash[i][j] = INF;
            }
        }
        dfsFirstPlayer(map, gaybrash, liChack, GAYBRASH, g, 0);
        bool OK = gaybrash[e.y][e.x] != INF;
        cout << (OK ? "YES" : "NO") << endl;
        for(int i = 0; i < m; i++){
            delete[] map[i];
        }
        delete[] map;
        for(int i = 0; i < m; i++){
            delete[] gaybrash[i];
        }
        delete[] gaybrash;
        for(int i = 0; i < m; i++){
            delete[] liChack[i];
        }
        delete[] liChack;
    }
    return 0;
}

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

#include <iostream>

#include <vector>

using namespace std;

const int INF = 10000000;

const string GAYBRASH = "GAYBRASH";

const string LICHACK = "LICHACK";

struct node{

int x;

int y;

};

vector<node> getChildrenBFS(char ** map, node parent, string hero){

string bannedChars = "R";

if(hero == LICHACK) bannedChars.push_back('e');

vector<node> children;

node leftChild = {parent.x - 1, parent.y};

node rightChild = {parent.x + 1, parent.y};

node downChild = {parent.x, parent.y + 1};

node upChild = {parent.x, parent.y - 1};

if(bannedChars.find(map[leftChild.y][leftChild.x]) == string::npos){

children.push_back(leftChild);

}

if(bannedChars.find(map[rightChild.y][rightChild.x]) == string::npos){

children.push_back(rightChild);

}

if(bannedChars.find(map[downChild.y][downChild.x]) == string::npos){

children.push_back(downChild);

}

if(bannedChars.find(map[upChild.y][upChild.x]) == string::npos){

children.push_back(upChild);

}

return children;

}

void dfsSecondPlayer(char ** map, int ** moves, string hero, node currentNode, int move){

moves[currentNode.y][currentNode.x] = move;

move++;

vector<node> children = getChildrenBFS(map, currentNode, hero);

vector<node> queue;

for(auto e: children) {

if (move < moves[e.y][e.x]) {

dfsSecondPlayer(map, moves, hero, e, move);

}

void dfsFirstPlayer(char ** map, int ** moves, int ** secondPlayer, string hero, node currentNode, int move){

moves[currentNode.y][currentNode.x] = move;

move++;

vector<node> children = getChildrenBFS(map, currentNode, hero);

vector<node> queue;

for(auto e: children){

if(move < moves[e.y][e.x] && move < secondPlayer[e.y][e.x]){

dfsFirstPlayer(map, moves, secondPlayer, hero, e, move);

}

int main() {

int tests;

cin >> tests;

for(; tests > 0; tests--){

int m;

int n;

cin >> m >> n;

cin.ignore();

node g;

node l;

node e;

char **map = new char*[m];

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

map[i] = new char[n];

}

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

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

map[i][j] = cin.get();

switch(map[i][j]){

case 'g':

g.x = j;

g.y = i;

break;

case 'l':

l.x = j;

l.y = i;

break;

case 'e':

e.x = j;

e.y = i;

break;

}

cin.ignore();

}

int **liChack = new int*[m];

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

liChack[i] = new int[n];

}

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

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

liChack[i][j] = INF;

}

dfsSecondPlayer(map, liChack, LICHACK, l, 0);

int **gaybrash = new int*[m];

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

gaybrash[i] = new int[n];

}

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

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

gaybrash[i][j] = INF;

}

dfsFirstPlayer(map, gaybrash, liChack, GAYBRASH, g, 0);

bool OK = gaybrash[e.y][e.x] != INF;

cout << (OK ? "YES" : "NO") << endl;

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

delete[] map[i];

}

delete[] map;

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

delete[] gaybrash[i];

}

delete[] gaybrash;

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

delete[] liChack[i];

}

delete[] liChack;

}

return 0;

}

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

Предположим, что существует безопасный для Гайбраша маршрут. Это означает, что Ли Чак не может перехватить его ни в одной точке этого маршрута, то есть, что в любую точку маршрута Гайбраш попадает как минимум на один ход раньше, чем Ли Чак. В противном случае безопасного хода нет.
Представим карту острова в виде неориентированного графа, вершинами которого в случае Гайбраша являются все участки, кроме участков с пометкой «R», а для Ли Чака — все участки, кроме участков с пометками «R» и «e». Две вершины будут соединяться ребром, если они соответствуют участкам, имеющим общую сторону. С помощью поиска в глубину найдем минимальное количество шагов, за которое Ли Чак попадает в каждую клетку, в которую он может попасть. Аналогично реализуем поиск в глубину для Гайбраша с той лишь разницей, что Гайбраш должен миновать те вершины графа, в которые он будет добираться дольше, чем Ли Чак. Если при этом найдется путь, соединяющий вершину, соответствующую начальному местоположению Гайбраша с вершиной, соответствующую цели, то он сможет спастись, в противном случае -нет.

Ссылки

Условие задачи на e-olymp
Решение на e-olymp
Код решения на Ideone

Related Images:

AL1

13/09/2016 by Станислав Коциевский

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

Вводится последовательность, состоящая из [latex]N[/latex] пар символов [latex](a_i, b_i)[/latex]. Каждая пара определяет порядок предшествования символов, например, пара [latex](b, c)[/latex] означает, что символ [latex]b[/latex] предшествует символу [latex]c[/latex]. Из порядка [latex](b, c)[/latex] и [latex](c, a)[/latex] следует порядок [latex](b, a)[/latex]. Необходимо определить, является ли введенная последовательность:

а) полной, т.е. все использованные для формирования пар символы (выбросив повторяющиеся) можно выстроить в цепочку [latex]A_{1},A_{2}, \cdots ,A_{s}[/latex] в порядке предшествования;

б) противоречивой, т.е. для некоторых символов [latex]x,y[/latex] можно получить одновременно порядок как [latex](x, y)[/latex] так и [latex](y, x)[/latex];

Тесты

Входные данные	Результат
4 a b b c c d b d	полный порядок
3 2 a 8 c c b	порядок неполный
3 2 a 8 c a 8	полный порядок
4 2 a 8 c c 2 a c	Порядок противоречив
10 a 5 5 4 b 3 3 4 5 3 b 5 a b 4 * * 0 4 0	полный порядок

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

#include <iostream>
#include <algorithm> //для использования функции sort
using namespace std;

int main()
{
    const int lch = 256;
    int n;
    cin>>n;
    
    char **p = new char* [n]; //Создаем массив p, где будем хранить пары символов.
    for (int i = 0; i < n; i++)
    {
        p[i] = new char [2];
    }
        
    for (int i = 0; i < n; i++)
    {
        cin >> p[i][1]>>p[i][2];
    }
    
    int chars[lch];
    for (int i = 0; i<lch; i++)
    {
        chars[i] = -1;
    }
    int K = 0;
    for (int i = 0; i<n; i++)
    {
        if (chars [ p[i][1]] == -1)
            K++;
        if (chars [ p[i][2]] == -1)
            K++;
        chars [ p[i][1]] = 0;
        chars [ p[i][2]] = 0;
    }
    
    bool change;
    char x, y;
    int M;
    for (int i = 0; i < n; i++)
    {
        change = false;
        for (int j = 0; j < n; j++)
        {
            x = p[j][1];
            y = p[j][2];
            M = max(chars[x] + 1, chars [y]);
            if (M > (K-1))
            {
                cout<<"Порядок противоречив";
                return 0;
            }
            if (chars[y] != M)
            {
                change = true;
            }
            chars[y] = M;
        }
        if (!change)
        {
            sort(chars, chars+lch);
            int previous = K;
            int i = lch-1;
            while (chars [i] > -1)
            {
                if (chars[i] == previous - 1)
                {
                    previous--;
                }
                else
                {
                    cout<<"порядок неполный";
                    return 0;
                }
                i--;
            }
            cout<<"полный порядок";
            return 0;
        }
    }
    return 0;
}

#include <iostream>

#include <algorithm> //для использования функции sort

using namespace std;

int main()

{

const int lch = 256;

int n;

cin>>n;

char **p = new char* [n]; //Создаем массив p, где будем хранить пары символов.

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

{

p[i] = new char [2];

}

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

{

cin >> p[i][1]>>p[i][2];

}

int chars[lch];

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

{

chars[i] = -1;

}

int K = 0;

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

{

if (chars [ p[i][1]] == -1)

K++;

if (chars [ p[i][2]] == -1)

K++;

chars [ p[i][1]] = 0;

chars [ p[i][2]] = 0;

}

bool change;

char x, y;

int M;

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

{

change = false;

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

{

x = p[j][1];

y = p[j][2];

M = max(chars[x] + 1, chars [y]);

if (M > (K-1))

{

cout<<"Порядок противоречив";

return 0;

}

if (chars[y] != M)

{

change = true;

}

chars[y] = M;

}

if (!change)

{

sort(chars, chars+lch);

int previous = K;

int i = lch-1;

while (chars [i] > -1)

{

if (chars[i] == previous - 1)

{

previous--;

}

else

{

cout<<"порядок неполный";

return 0;

}

i--;

}

cout<<"полный порядок";

return 0;

}

return 0;

}

Решение

Общая идея решения

Эта часть решения взята отсюда.

Пусть при записи этих [latex]N[/latex] пар встретилось всего [latex]K[/latex] различных символов, которые образуют множество [latex]X[/latex].

Идея решения задачи состоит в последовательном присвоении каждому символу [latex]s[/latex] из [latex]X[/latex] номера, который определяет количество [latex]P(s)[/latex] элементов, предшествующих ему, с учетом свойства транзитивности (из [latex](c, b)[/latex] и [latex](b, a)[/latex] следует [latex](c, a)[/latex]). Это осуществляется следующим образом:

Первоначально предполагается, что каждому символу не предшествует ни один символ, т.е. [latex]P(s)=0[/latex] для любого [latex]s[/latex].

При просмотре очередной пары [latex](x, y)[/latex] символу y присваивается большее из значений [latex]P(x)+1, P(y)[/latex].

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

Не произошло изменения ни одного из номеров символов. Если при этом номера символов различны и лежат в пределах от 0 до [latex]K-1[/latex], то эта нумерация определяет полный порядок. Иначе порядок неполный.
Номер некоторого символа превысил [latex]K-1[/latex]. Это произошло потому, что рост номеров неограничен, т.е. осуществляется циклически. Следовательно порядок противоречив.

Легко понять, что число просмотров не превысит [latex]N[/latex].

Некоторые аспекты реализации

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

Воспользуемся тем фактом, что символы воспринимаются компьютером, как числа. Заведем для номеров символов в последовательности массив chars на 256 элементов, поскольку тип данных char может принимать значения от 0 до 255. Это позволит обращаться к элементу массива, соответствующий какому-то символу напрямую, а не используя ассоциативный массив. Это дает выигрыш в скорости, хотя и с некоторым увеличением расхода памяти.

Изначально каждый элемент массива chars пусть будет равен -1. Затем, пройдя все пары, присвоим каждому символу номер 0 в этом массиве. Таким образом, мы в дальнейшем сможем определить, что символ входит в нашу последовательность, поскольку его номер неотрицательный.

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

ссылка на код на ideone

ссылка на условие задачи

Related Images:

Лабиринт

02/07/2016 by Маша Лукьянова

Условие:

Имя входного файла: стандартный поток ввода

Имя выходного файла: стандартный поток вывода

Ограничение по времени: 2 second

Ограничение по памяти: 64 мегабайт

Задан лабиринт [latex] N \times N [/latex], некоторые клетки которого могут быть заняты. Дан путь робота длины [latex] k [/latex] по этому лабиринту без указания его начального положения. Известно, что робот до начала движения стоит в одной из свободных клеток. Необходимо определить наименьшее количество передвижений по пути, после которого можно точно определить, где находится робот.

Задача взята из 1-го раунда KPI OPEN 2013 года.

Формат входного файла:

Первая строка входного файла содержит два целых числа через пробел $$ N (1 \leq N \leq 100) $$ и $$k (0 \leq k \leq 10^{5}) $$. В следующих [latex] N [/latex] строках задана карта лабиринта как совокупность 0 и 1 без пробелов: 1 – занятая клетка, 0 – свободная. В последней строке дана последовательность из $$ k (0 \leq k \leq 10^{5} ) $$ символов. Символы задают движение робота по лабиринту: символ [latex] U [/latex] — вверх, [latex] D [/latex] — вниз, [latex] R [/latex] —вправо, [latex] L [/latex] — влево. Других символов в строке передвижений нет, все символы в верхнем регистре латиницы.

Формат выходного файла:

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

Тесты:

№	Входные данные	Выходные данные
1	2 0 11 01	0
2	2 0 11 11	-1
3	2 1 11 01 R	-1
4	3 3 000 010 000 RDU	2
5	5 5 00010 10001 00100 10100 01101 RDUUU	4

Решение:

Если попробовать решить эту задачу «в лоб», то решение не будет удовлетворять пределу по времени, так как в худшем случае, нам надо перебрать $$ 10^{4} $$ возможных начальных позиций и совершить из них $$ 10^{5} $$ ходов, что в результате дает $$ 10^{9} $$ операций.

Решение «в лоб»:

Заведем список позиций в лабиринте, которым соответствуют элементы матрицы, в которые может попасть робот. В изначальном состоянии, без просмотра пути передвижения робота, это будут все позиции в лабиринте, где значение равно $$ 0 $$. После чего, проходя путь робота по шагам, будем для всех позиций в списке проверять:
- Если мы вышли за границу матрицы, или в клетке, в которую мы собираемся перейти стоит $$ 1 $$, тогда удаляем эту позицию, поскольку она для нас недостижима.
- Иначе ничего не делаем.
Если количество текущих вариантов пути стало равным $$ 1 $$, то мы запоминаем количество ходов при которой была достигнута данная ситуация.
Так будем делать до тех пор, пока робот закончил свой путь.
Если после всех проделанных нами операций остался один вариант полностью пройденного пути, тогда ответ найден. А именно это будет ход, после которого у нас кол-во удовлетворяющих позиций стало равным $$ 1 $$. В любом другом случае ответ нельзя определить однозначно.

Другая идея состоит в том, чтобы построить карту «переходов», в которой будет храниться номер хода, на котором робот впервые попал в эту клетку и ее координаты. Эта карта играет роль некоторого шаблона полного пути робота и «накладывая» его на каждый элемент матрицы в качестве начальной позиции, мы проверяем мог ли данный элемент матрицы служить «пунктом отправления» робота. Если такой элемент есть и он единственен, значит, можно однозначно определить начальное положение робота, но для того чтобы определить минимальное количество требуемых ходов-нужно последовательно удалять последние ходы из карты, «накладывая» изменившийся шаблон на каждый элемент, до тех пор, пока количество элементов удовлетворяющих шаблону не возрастет. Что значит, что мы получим номер решающего хода после которого судьба робота решится однозначно, значит ответом будет предыдущий ход. Стоит отметить, что если в карте останется всего лишь один элемент (соответствующий первому ходу), то расположение робота определялось однозначно первым ходом.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <set>
#include <list>
#include <map>
 
#define ll long long int
#define X first
#define Y second
#include <iostream>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    char maze[n][n];//лабиринт
    for(int i = 0; i < n; ++i){
        getchar();
        for(int j = 0; j < n; ++j){
            maze[i][j] = getchar();
        }
    }
    getchar();
    char path[k+1]; //путь
    for(int i = 0; i < k; ++i){
        path[i + 1] = getchar();
    }
    set<pair<int, int> > visited; 
        //ячейки, в которых мы побывали
    map<int, pair<int, int> > nodes; 
        // узлы, которые должен пройти робот (номер хода, координаты)
    pair<int, int> cur = {0, 0};
    visited.insert(cur);
    nodes[0] = cur; 
    //проходим весь путь
    for(int i = 1; i <= k; ++i){
        if(path[i] == 'L'){
            --cur.X;
            if(!visited.count(cur)){
                nodes[i] = cur;
                visited.insert(cur);
            }
        }else if(path[i] == 'R'){
            ++cur.X;
            if(!visited.count(cur)){
                nodes[i] = cur;
                visited.insert(cur);
            }
        }else if(path[i] == 'U'){
            --cur.Y;
            if(!visited.count(cur)){
                nodes[i] = cur;
                visited.insert(cur);
            }
        }else if(path[i] == 'D'){
            ++cur.Y;
            if(!visited.count(cur)){
                nodes[i] = cur;
                visited.insert(cur);
            }
        }
    }
    int count = 0;
    map<int, int> ans; bool ok = false;
    for(; nodes.size();){
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j){
                for(pair<int, pair<int, int> > a : nodes){
                    if(j + a.Y.X < 0 || j + a.Y.X >= n ||
                              // не вышли ли за пределы по строкам
                        i + a.Y.Y < 0 || i + a.Y.Y >= n || 
                              // не вышли ли за пределы по столбцам
                        maze[i + a.Y.Y][j + a.Y.X] == '1'){ 
                              //не попали ли на 1-цу
                        --count;
                        break;
                    }
                }
                ++count;
            }
        }
        auto t = --nodes.end();
        ans[count] = t->X;
        nodes.erase(t);
        count = 0;
        if(ans.size() == 2) break;
        if(!ok){
            ok = 1;
            if(ans.begin()->X != 1){
                cout << -1 << endl;
                return 0;
            }
        }
    }
    if(ans.size() == 1 && ans.begin()->X == 1){
        cout << ans.begin()->Y << endl;
    }else if(ans.size() == 2 && ans.begin()->X == 1){
        cout << ans.begin()->Y << endl;
    }else{
        cout << -1 << endl;
    }
}

100

101

102

103

104

105

106

#include <iostream>

#include <vector>

#include <string>

#include <algorithm>

#include <stack>

#include <set>

#include <list>

#include <map>

#define ll long long int

#define X first

#define Y second

#include <iostream>

using namespace std;

int main() {

int n, k;

cin >> n >> k;

char maze[n][n];//лабиринт

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

getchar();

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

maze[i][j] = getchar();

}

getchar();

char path[k+1]; //путь

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

path[i + 1] = getchar();

}

set<pair<int, int> > visited;

//ячейки, в которых мы побывали

map<int, pair<int, int> > nodes;

// узлы, которые должен пройти робот (номер хода, координаты)

pair<int, int> cur = {0, 0};

visited.insert(cur);

nodes[0] = cur;

//проходим весь путь

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

if(path[i] == 'L'){

--cur.X;

if(!visited.count(cur)){

nodes[i] = cur;

visited.insert(cur);

}

}else if(path[i] == 'R'){

++cur.X;

if(!visited.count(cur)){

nodes[i] = cur;

visited.insert(cur);

}

}else if(path[i] == 'U'){

--cur.Y;

if(!visited.count(cur)){

nodes[i] = cur;

visited.insert(cur);

}

}else if(path[i] == 'D'){

++cur.Y;

if(!visited.count(cur)){

nodes[i] = cur;

visited.insert(cur);

}

int count = 0;

map<int, int> ans; bool ok = false;

for(; nodes.size();){

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

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

for(pair<int, pair<int, int> > a : nodes){

if(j + a.Y.X < 0 || j + a.Y.X >= n ||

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

i + a.Y.Y < 0 || i + a.Y.Y >= n ||

// не вышли ли за пределы по столбцам

maze[i + a.Y.Y][j + a.Y.X] == '1'){

//не попали ли на 1-цу

--count;

break;

}

++count;

}

auto t = --nodes.end();

ans[count] = t->X;

nodes.erase(t);

count = 0;

if(ans.size() == 2) break;

if(!ok){

ok = 1;

if(ans.begin()->X != 1){

cout << -1 << endl;

return 0;

}

if(ans.size() == 1 && ans.begin()->X == 1){

cout << ans.begin()->Y << endl;

}else if(ans.size() == 2 && ans.begin()->X == 1){

cout << ans.begin()->Y << endl;

}else{

cout << -1 << endl;

}

Submission.

Related Images:

e-olymp 1060. Линии

28/06/2016 by Кондратюк Настя

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

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

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

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

В первой строке находится число [latex]n \left (2\leq n\leq 40 \right )[/latex], в каждой из следующих [latex]n[/latex] строк — по [latex]n[/latex] символов. Символом точки обозначена свободная клетка, латинской заглавной [latex]O[/latex] — шарик, [latex]@[/latex] — исходное положение шарика, который должен двигаться, латинской заглавной [latex]X[/latex] — конечное положение шарика.

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

В первой строке выводится [latex]Y[/latex], если движение возможно, или [latex]N[/latex], если нет. Если движение возможно далее следует [latex]n[/latex] строк по [latex]n[/latex] символов — как и на вводе, но [latex]X[/latex], а также все точки на пути заменяются плюсами.

Тесты

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

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

5
....X
.OOOO
.....
OOOO.
@....

....X

.OOOO

.....

OOOO.

@....

Y
+++++
+OOOO
+++++
OOOO+
@++++

+++++

+OOOO

+++++

OOOO+

@++++

5
..X..
.....
OOOOO
.....
..@..

..X..

.....

OOOOO

.....

..@..

N

5
...X.
.....
O.OOO
.....
....@

...X.

.....

O.OOO

.....

....@

Y
..++.
.++..
O+OOO
.++++
....@

..++.

.++..

O+OOO

.++++

....@

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

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

/* нахождение пути*/
void find_path(int n, int row, int col, char** lab, int** visited, int** path, queue<int>& plan){
    if(!visited[row][col]){
        /* проверяем не вышли ли мы за границы лабиринта, есть ли клетка 
        в массиве посещенных и можно ли через нее пройти*/
        if ((row+1) < n && (row+1) >= 0 && !visited[row+1][col] &&
            (lab[row+1][col] == '.' || lab[row+1][col] == 'X')) {
                path[row+1][col] = path[row][col] + 1;
                plan.push(row+1);
                plan.push(col);
        }
        if((row-1) < n && (row-1) >= 0 && !visited[row-1][col] && 
            (lab[row-1][col] == '.' || lab[row-1][col] == 'X')) {
                path[row-1][col] = path[row][col] + 1;
                plan.push(row-1);
                plan.push(col);
        }
        if((col + 1) < n && (col + 1) >= 0 && !visited[row][col+1] && 
            (lab[row][col+1] == '.' || lab[row][col+1] == 'X')) {
                path[row][col+1] = path[row][col] + 1;
                plan.push(row);
                plan.push(col+1);
        }
        if((col - 1) < n && (col - 1) >= 0 && !visited[row][col-1] && 
            (lab[row][col-1] == '.' || lab[row][col-1] == 'X')) {
                path[row][col-1] = path[row][col] + 1;
                plan.push(row);
                plan.push(col-1);
        }
        visited[row][col] = 1; /* отмечаем клетку в которой побывали */
    }
}
 
int main() {
    int n, x_start, y_start, x_end, y_end, x, y;
    queue <int> plan; 
    cin >> n;
    char** lab = new char* [n];
    int** visited = new int * [n];
    int** path = new int * [n];
    for(int i=0; i<n; i++){
        lab[i] = new char [n];   /* массив для хранения лабиринта */
        visited[i] = new int [n]; /* массив для хранения информации о посещении клеток*/
        path[i] = new int [n];  /* массив для хранения найденных путей */
        for(int j=0; j<n; j++){
            visited[i][j] = 0;  
            path[i][j] = -1;   
            cin >> lab[i][j]; 
            if (lab[i][j] == '@') { /* находим начало пути*/
                x_start = i;
                y_start = j;
                plan.push(i);  /* заносим начальную клетку */
                plan.push(j);  /* в план посещения */
                path[i][j] = 1;
            }
            else if (lab[i][j] == 'X') { /* находим конечную точку */
                x_end = i;
                y_end = j;
            }
        }
    }
    while(!plan.empty()){ /* пока очередь посещения клеток непустая*/
        x=plan.front();
        plan.pop();
        y=plan.front();
        plan.pop();
        find_path(n, x, y, lab, visited, path, plan); /* продолжаем поиск пути*/
    }
    if(!visited[x_end][y_end]){
        cout << "N" << endl;
    }
    else {
        cout << "Y" << endl;
            x = x_end;
            y = y_end;
            lab[x][y] = '+';
            while (path[x][y] != 2) { /* восстановление пути*/
                if ((x-1) >= 0 && (x-1) < n && (path[x-1][y] == path[x][y] - 1)) {
                    x = x-1;
                    lab[x][y] = '+';
                }
                else if ((x+1) >= 0 && (x+1) < n && (path[x+1][y] == path[x][y] - 1)) {
                    x = x+1;
                    lab[x][y] = '+';
                }
                else if ((y-1) >= 0 && (y-1) < n && (path[x][y-1] == path[x][y] - 1)) {
                    y = y-1;
                    lab[x][y] = '+';
                }
                else if ((y+1) >= 0 && (y+1) < n && (path[x][y+1] == path[x][y] - 1)) {
                    y = y+1;
                    lab[x][y] = '+';
                }
            }
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    cout << lab[i][j];
                }
                cout << endl;
            }
        }
    return 0;
}

100

101

102

103

104

105

106

107

#include <iostream>

#include <queue>

using namespace std;

/* нахождение пути*/

void find_path(int n, int row, int col, char** lab, int** visited, int** path, queue<int>& plan){

if(!visited[row][col]){

/* проверяем не вышли ли мы за границы лабиринта, есть ли клетка

в массиве посещенных и можно ли через нее пройти*/

if ((row+1) < n && (row+1) >= 0 && !visited[row+1][col] &&

(lab[row+1][col] == '.' || lab[row+1][col] == 'X')) {

path[row+1][col] = path[row][col] + 1;

plan.push(row+1);

plan.push(col);

}

if((row-1) < n && (row-1) >= 0 && !visited[row-1][col] &&

(lab[row-1][col] == '.' || lab[row-1][col] == 'X')) {

path[row-1][col] = path[row][col] + 1;

plan.push(row-1);

plan.push(col);

}

if((col + 1) < n && (col + 1) >= 0 && !visited[row][col+1] &&

(lab[row][col+1] == '.' || lab[row][col+1] == 'X')) {

path[row][col+1] = path[row][col] + 1;

plan.push(row);

plan.push(col+1);

}

if((col - 1) < n && (col - 1) >= 0 && !visited[row][col-1] &&

(lab[row][col-1] == '.' || lab[row][col-1] == 'X')) {

path[row][col-1] = path[row][col] + 1;

plan.push(row);

plan.push(col-1);

}

visited[row][col] = 1; /* отмечаем клетку в которой побывали */

}

int main() {

int n, x_start, y_start, x_end, y_end, x, y;

queue <int> plan;

cin >> n;

char** lab = new char* [n];

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

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

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

lab[i] = new char [n]; /* массив для хранения лабиринта */

visited[i] = new int [n]; /* массив для хранения информации о посещении клеток*/

path[i] = new int [n]; /* массив для хранения найденных путей */

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

visited[i][j] = 0;

path[i][j] = -1;

cin >> lab[i][j];

if (lab[i][j] == '@') { /* находим начало пути*/

x_start = i;

y_start = j;

plan.push(i); /* заносим начальную клетку */

plan.push(j); /* в план посещения */

path[i][j] = 1;

}

else if (lab[i][j] == 'X') { /* находим конечную точку */

x_end = i;

y_end = j;

}

while(!plan.empty()){ /* пока очередь посещения клеток непустая*/

x=plan.front();

plan.pop();

y=plan.front();

plan.pop();

find_path(n, x, y, lab, visited, path, plan); /* продолжаем поиск пути*/

}

if(!visited[x_end][y_end]){

cout << "N" << endl;

}

else {

cout << "Y" << endl;

x = x_end;

y = y_end;

lab[x][y] = '+';

while (path[x][y] != 2) { /* восстановление пути*/

if ((x-1) >= 0 && (x-1) < n && (path[x-1][y] == path[x][y] - 1)) {

x = x-1;

lab[x][y] = '+';

}

else if ((x+1) >= 0 && (x+1) < n && (path[x+1][y] == path[x][y] - 1)) {

x = x+1;

lab[x][y] = '+';

}

else if ((y-1) >= 0 && (y-1) < n && (path[x][y-1] == path[x][y] - 1)) {

y = y-1;

lab[x][y] = '+';

}

else if ((y+1) >= 0 && (y+1) < n && (path[x][y+1] == path[x][y] - 1)) {

y = y+1;

lab[x][y] = '+';

}

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

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

cout << lab[i][j];

}

cout << endl;

}

return 0;

}

ideone.com

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

Решение

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

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

Related Images:

А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]
По алгоритму нахождения максимума находим длину наибольшего отрезка.
Выводим матрицу.
Выводим длину наибольшего отрезка.
Ссылка на код

Related Images:

А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. Вывод массива.

Ссылка на код

Related Images:

А705

29/06/2015 by Кібакова Надія Олександрівна

Задача:
Даны квадратные матрицы [latex]A[/latex] и [latex]B[/latex] порядка [latex]n[/latex]. Получить матрицу [latex]A(B-E)+C[/latex], где [latex]E[/latex] — единичная матрица порядка [latex]n[/latex], а элементы матрицы [latex]C[/latex] вычисляются по формуле:[latex]C_{ij}=\frac{1}{i+j}\;\;\;\;(i,j=1,2,\ldots,n)[/latex].

Тесты
К сожалению я не разместила здесь тесты к задаче.

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

Код C++

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;                                             //ввод из стандартного потока
    int A[n][n];                                        
    int B[n][n];
    int Z[n][n];
    int H[n][n];
    int E[n][n];
    float C[n][n];
    float Ans[n][n];
    
    for (int i = 0; i < n; i++){             //матрица А
        for (int j = 0 ; j < n ; j++){
            cin >> A[i][j];
        }
    }
    
    for (int i = 0; i < n; i++){                            //матрица В
        for (int j = 0 ; j < n ; j++){
            cin >> B[i][j];
        }
    }
    
    for (int i = 0; i < n; i++){                            //единичная матрица Е
        for (int j = 0 ; j < n ; j++){
            if (i == j) E[i][j] = 1;
            else E[i][j] = 0;
        }
    }
 
    for (int i = 0; i < n; i++){                 //разность матриц В и Е
        for (int j = 0; j < n; j++){
            Z[i][j] = 0;
            Z[i][j] = B[i][j] - E[i][j];
        }
    }
    
    for (int i = 0; i < n; i++){             //умножение матриц А и (В - Е)
        for (int j = 0; j < n; j++){
            H[i][j] = 0;
            for (int t = 0; t < n; t++){
                H[i][j] += A[i][t] * Z[t][j];
            }
        }
    }
    
    for (int i = 0; i < n; i++){             //матрица С
        for (int j = 0; j < n; j++){
            C[i][j] = 0;
            C[i][j] = 1.0/(i+1 + j+1);
        }
    }
    
    for (int i = 0; i < n; i++){                 //матрица A(B–E)+C
        for(int j = 0; j < n; j++){
            Ans[i][j] = H[i][j] + C[i][j];
            printf("%1.2f", Ans[i][j]); 
             cout << " " ;
        }
        cout << endl;
    }
    
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n; //ввод из стандартного потока

int A[n][n];

int B[n][n];

int Z[n][n];

int H[n][n];

int E[n][n];

float C[n][n];

float Ans[n][n];

for (int i = 0; i < n; i++){ //матрица А

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

cin >> A[i][j];

}

for (int i = 0; i < n; i++){ //матрица В

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

cin >> B[i][j];

}

for (int i = 0; i < n; i++){ //единичная матрица Е

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

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

else E[i][j] = 0;

}

for (int i = 0; i < n; i++){ //разность матриц В и Е

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

Z[i][j] = 0;

Z[i][j] = B[i][j] - E[i][j];

}

for (int i = 0; i < n; i++){ //умножение матриц А и (В - Е)

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

H[i][j] = 0;

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

H[i][j] += A[i][t] * Z[t][j];

}

for (int i = 0; i < n; i++){ //матрица С

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

C[i][j] = 0;

C[i][j] = 1.0/(i+1 + j+1);

}

for (int i = 0; i < n; i++){ //матрица A(B–E)+C

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

Ans[i][j] = H[i][j] + C[i][j];

printf("%1.2f", Ans[i][j]);

cout << " " ;

}

cout << endl;

}

return 0;

}

Код C++ на Ideone: A705

Код Java

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

class Ideone {
    public static void main (String[] args) throws java.lang.Exception {
        Scanner read = new Scanner (System.in); 
        int n = read.nextInt();                                         //ввод из стандартного потока
        double A[][] = new double [n][n];                                       
        double B[][] = new double [n][n];
        double Z[][] = new double [n][n];
        double H[][] = new double [n][n];
        double E[][] = new double [n][n];
        double C[][] = new double [n][n];
        double Ans[][] = new double [n][n];
    
        for (int i = 0; i < n; i++){             //матрица А
            for (int j = 0 ; j < n ; j++){
                A[i][j] = read.nextDouble();
            }
        }
    
        for (int i = 0; i < n; i++){                            //матрица В
            for (int j = 0 ; j < n ; j++){
                B[i][j] =  read.nextDouble();
            }
        }
    
        for (int i = 0; i < n; i++){                            //единичная матрица Е
            for (int j = 0 ; j < n ; j++){
                if (i == j) E[i][j] = 1;
                else E[i][j] = 0;
            }
        }
     
        for (int i = 0; i < n; i++){                 //разность матриц В и Е
            for (int j = 0; j < n; j++){
                Z[i][j] = 0;
                Z[i][j] = B[i][j] - E[i][j];
            }
        }
        
        for (int i = 0; i < n; i++){             //умножение матриц А и (В - Е)
            for (int j = 0; j < n; j++){
                H[i][j] = 0;
                for (int t = 0; t < n; t++){
                    H[i][j] += A[i][t] * Z[t][j];
                }
            }
        }
        
        for (int i = 0; i < n; i++){             //матрица С
            for (int j = 0; j < n; j++){
                C[i][j] = 0;
                C[i][j] = 1.0/((i+1)+(j+1));
            }
        }
        
        for (int i = 0; i < n; i++){                 //матрица A(B–E)+C
            for(int j = 0; j < n; j++){
                Ans[i][j] = H[i][j] + C[i][j];
                System.out.print(Ans[i][j] + " "); 
            }
            System.out.println();
        }
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone {

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

Scanner read = new Scanner (System.in);

int n = read.nextInt(); //ввод из стандартного потока

double A[][] = new double [n][n];

double B[][] = new double [n][n];

double Z[][] = new double [n][n];

double H[][] = new double [n][n];

double E[][] = new double [n][n];

double C[][] = new double [n][n];

double Ans[][] = new double [n][n];

for (int i = 0; i < n; i++){ //матрица А

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

A[i][j] = read.nextDouble();

}

for (int i = 0; i < n; i++){ //матрица В

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

B[i][j] = read.nextDouble();

}

for (int i = 0; i < n; i++){ //единичная матрица Е

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

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

else E[i][j] = 0;

}

for (int i = 0; i < n; i++){ //разность матриц В и Е

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

Z[i][j] = 0;

Z[i][j] = B[i][j] - E[i][j];

}

for (int i = 0; i < n; i++){ //умножение матриц А и (В - Е)

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

H[i][j] = 0;

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

H[i][j] += A[i][t] * Z[t][j];

}

for (int i = 0; i < n; i++){ //матрица С

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

C[i][j] = 0;

C[i][j] = 1.0/((i+1)+(j+1));

}

for (int i = 0; i < n; i++){ //матрица A(B–E)+C

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

Ans[i][j] = H[i][j] + C[i][j];

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

}

System.out.println();

}

Код Java на Ideone: A705

Тесты:

№ теста	Размерность матрицы n	Матрица A	Матрица В	Ответ
1	2	3 4 2 1	2 1 9 0	39.50 -0.67 11.33 1.25
2	4	5 5 5 5 0 0 8 7 2 3 4 7 8 6 1 2	5 7 3 4 9 8 3 4 2 3 4 5 6 6 6 6	105.50 115.33 75.25 90.20 58.33 66.25 66.20 75.17 85.25 89.20 69.17 75.14 100.20 113.17 57.14 71.12
3	3	0 0 0 0 0 0 0 0 0	1 0 0 0 1 0 0 0 1	0.5 0.33 0.25 0.33 0.25 0.20 0.25 0.20 0.17

Related Images:

А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' : ' ');

}

Related Images:

А703

19/06/2015 by Стеблинський Ігор Віталійович

Задача

Даны квадратная матрица [latex]A[/latex] порядка [latex]n[/latex], векторы [latex]x[/latex] и [latex]y[/latex] с [latex]n[/latex] элементами. Получить вектор [latex]A(x+y)[/latex].

Примеры:

Размерность матрицы	Матрица	Вектор x	Вектор y	Результирующий вектор A(x+y)
2	2 3 3 2	3 4	5 6	46 44
3	2 1 4 5 2 6 3 4 8	2 2 2	4 4 4	42 78 90
4	1 2 3 4 3 4 1 6 2 3 8 1 4 5 0 8	1 2 3 4	5 4 3 2	60 84 84 102
5	0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0	4 6 7 8 0	2 8 9 3 1	0 0 16 0 0

Алгоритм решения: Вводим матрицу [latex]A[/latex] порядка [latex]n[/latex]. Вводим векторы [latex]x[/latex] и [latex]y[/latex], прибавляем векторы [latex]x[/latex] и [latex]y[/latex]. После умножаем матрицу [latex]A[/latex] на вектор [latex]x + y[/latex] и получаем вектор [latex]A(x + y)[/latex]. С помощью цикла выводим результирующий вектор.

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

#include <iostream>
using namespace std;
 
int main() {
	int n;
	cin >> n;
	int x[n];
	int y[n];
	int z[n];
	int A[n][n];
	 int result_vector[n];
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++) 
			cin >> A[i][j];
	}
	for (int i = 0; i < n; i++){ 
		cin>>x[i];
	}
	for (int i = 0; i < n; i++){ 
		cin>>y[i];
	}
	for (int i = 0; i < n; i++){
		z[i]=x[i]+y[i];            
	}
	for(int i=0; i<n; i++)
	{
		result_vector[i]=0;							
		for(int j=0; j<n; j++)
		{
			result_vector[i]+=A[i][j]*z[j];  
		}
	}	
	for(int i=0; i<n; i++)
	{
		cout << result_vector[i] << endl;			
	}
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

int x[n];

int y[n];

int z[n];

int A[n][n];

int result_vector[n];

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

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

cin >> A[i][j];

}

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

cin>>x[i];

}

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

cin>>y[i];

}

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

z[i]=x[i]+y[i];

}

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

{

result_vector[i]=0;

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

{

result_vector[i]+=A[i][j]*z[j];

}

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

{

cout << result_vector[i] << endl;

}

return 0;

}

Оригинал кода можно увидеть перейдя по ссылке

import java.util.*;
import java.lang.*;
import java.io.*;
 
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int n;
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		double []x = new double[n];
		double []y = new double[n];
		double []z = new double[n];
		double [] result_vector = new double[n];
		double [][] A = new double[n][n];
		for (int i = 0; i < n; i++){
			for (int j = 0; j < n; j++){ 
				A[i][j]=in.nextDouble();
			}	
		}
		for (int i = 0; i < n; i++){ 
			x[i]=in.nextDouble();
		}
		for (int i = 0; i < n; i++){ 
			y[i]=in.nextDouble();
		}
		for (int i = 0; i < n; i++){
			z[i]=x[i]+y[i];            
		}
		for(int i=0; i<n; i++)
		{
			result_vector[i]=0;							
			for(int j=0; j<n; j++)
			{
				result_vector[i]+=A[i][j]*z[j];  
			}
		}	
		for(int i=0; i<n; i++)
		{
			System.out.printf("%.6f ",result_vector[i]);			
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class Ideone

{

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

{

int n;

Scanner in = new Scanner(System.in);

n = in.nextInt();

double []x = new double[n];

double []y = new double[n];

double []z = new double[n];

double [] result_vector = new double[n];

double [][] A = new double[n][n];

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

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

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

}

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

x[i]=in.nextDouble();

}

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

y[i]=in.nextDouble();

}

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

z[i]=x[i]+y[i];

}

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

{

result_vector[i]=0;

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

{

result_vector[i]+=A[i][j]*z[j];

}

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

{

System.out.printf("%.6f ",result_vector[i]);

}

Оригинал кода можно увидеть перейдя по ссылка

Related Images:

А700в

19/06/2015 by Янішевська Альона Русланівна

Задача. Дана квадратная матрица А порядка n. Получить матрицу AB; элементы матрицы B вычисляются по формуле:

[latex]b_{ij}=\left\{\begin{matrix}\frac{1}{i+j-1}&,if\: i<j\\ 0&,if\: i=j\\-\frac{1}{i+j-1}&other\: case\end{matrix}\right.[/latex]

[latex](i,j=1,\cdots, n)[/latex]

Тесты:

Размер матрицы	Входные данные	Результат	Комментарий
n=2	[latex]\begin{pmatrix}1&7\\3&2\end{pmatrix}[/latex]	[latex]\begin{pmatrix}-3,5&0,5\\-1&1,5\end{pmatrix}[/latex]	Пройден
n=3	[latex]\begin{pmatrix}1&2&3\\7&6&5\\4&8&9\end{pmatrix}[/latex]	[latex]\begin{pmatrix}-2&-0,25&0,83333\\-4,66667&2,25&3,83333\\-7&-0,25&3,333\end{pmatrix}[/latex]	Пройден

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

#include <iostream>
 
using namespace std;
 
int main() {
	int n;
	cin >> n;
	double A[n][n];
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			cin >> A[i][j];
		}
	}
 
	double B[n][n];
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			B[i][j] = 0;
			if (i < j){B[i][j] = 10 * 0.1 / ((i+1) + (j+1) -1);}
			else {
				if (i == j){B[i][j] = 0;}
				else {B[i][j] = -10 * 0.1 / ((i+1) + (j+1) -1);}
			}	
		}
	}
 
	double C[n][n];
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			C[i][j] = 0;
			for(int k = 0; k < n; k++){
				C[i][j] += A[i][k] * B[k][j];
			}
		}
	}

	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			cout << C[i][j] << " ";
		}
		cout << endl;
	}
 
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

double A[n][n];

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

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

cin >> A[i][j];

}

double B[n][n];

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

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

B[i][j] = 0;

if (i < j){B[i][j] = 10 * 0.1 / ((i+1) + (j+1) -1);}

else {

if (i == j){B[i][j] = 0;}

else {B[i][j] = -10 * 0.1 / ((i+1) + (j+1) -1);}

}

double C[n][n];

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

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

C[i][j] = 0;

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

C[i][j] += A[i][k] * B[k][j];

}

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

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

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

}

cout << endl;

}

return 0;

}

После ввода матрицы A, мы должны найти элементы матрицы B. Из условия задачи: [latex]b_{ij}=\left\{\begin{matrix}\frac{1}{i+j-1}&,if\: i<j\\ 0&,if\: i=j\\-\frac{1}{i+j-1}&other\: case\end{matrix}\right.[/latex] , при [latex](i,j=1,\cdots, n)[/latex].

Для нахождения [latex]b_{ij}[/latex] используется условный оператор if в цикле for. Матрица C — результат умножения матрицы A на матрицу B, которое также производим в цикле for.

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

Решение на Java:

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

class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner  in = new Scanner(System.in);
		int  n = in.nextInt();
		double A[][];
		A = new double [n][];
		for(int i=0; i<n; i++){
			A[i] = new double [n];   
			for(int j=0; j<n; j++){
				A[i][j] = in.nextDouble();
			}
		}
		double B[][];
		B = new double [n][];
		for(int i=0; i<n; i++){
			B[i] = new double [n];  
			for(int j=0; j<n; j++){
				B[i][j]=0;
				if (i<j){
					B[i][j]=10*0.1/((i+1)+(j+1)-1);
				}
				else{
					if (i==j){
						B[i][j]=0;
					}
					else {
							B[i][j]=-10*0.1/((i+1)+(j+1)-1);
					}
				}	
			}
		}
		double C[][];
    	C = new double [n][];
		for(int i=0; i<n; i++){
		 	C[i] = new double [n];  
			for(int j=0; j<n; j++){
				C[i][j]=0;
				for(int k=0; k<n; k++){
					C[i][j]+=A[i][k]*B[k][j];
				}
			}
		}
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				System.out.print(C[i][j]+" "); 
			}
		System.out.println();
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

double A[][];

A = new double [n][];

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

A[i] = new double [n];

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

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

}

double B[][];

B = new double [n][];

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

B[i] = new double [n];

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

B[i][j]=0;

if (i<j){

B[i][j]=10*0.1/((i+1)+(j+1)-1);

}

else{

if (i==j){

B[i][j]=0;

}

else {

B[i][j]=-10*0.1/((i+1)+(j+1)-1);

}

double C[][];

C = new double [n][];

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

C[i] = new double [n];

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

C[i][j]=0;

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

C[i][j]+=A[i][k]*B[k][j];

}

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

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

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

}

System.out.println();

}

Ссылка на решение.

Related Images:

А704

18/06/2015 by Карагяур Мілан Сергійович

Задача: Даны квадратные матрицы A, B и C порядка n. Получить матрицу (A+B)C.

Решение: В первом цикле читаем матрицу A. Во втором цикле читаем матрицу B и сразу прибавляем ее к матрице A, получаем сумму матриц. В третьем цикле умножаем сумму матриц A и B на матрицу C и выводим результат.

Код:

#include <iostream>
#include <cstdlib>
 
using namespace std;
int main(){
	int n;
	cin >> n;
	int a[n][n], b[n][n], c[n][n], d[n][n];
 
	for( int i=0 ; i<n ; i++ ){
		for( int j=0 ; j<n ; j++ ){ 
			cin >> a[i][j];
		}
	}
	for( int i=0 ; i<n ; i++ ){
		for( int j=0 ; j<n ; j++ ){
			cin >> b[i][j];
			a[i][j] += b[i][j];
		}
	}
	for( int i=0 ; i<n ; i++ ){
		for( int j=0 ; j<n ; j++ ){
			cin >> c[i][j];
		}
	}
	for( int i=0 ; i<n ; i++ ){		
		for( int j=0 ; j<n ; j++,d[i][j]=0 ){			
			for( int k=0 ; k<n ; k++ ){			
				d[i][j] += a[i][k] * c[k][j];
			}
			cout << d[i][j] << (j+1 == n? '\n' : ' ' );
		}
	}
}

#include <iostream>

#include <cstdlib>

using namespace std;

int main(){

int n;

cin >> n;

int a[n][n], b[n][n], c[n][n], d[n][n];

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

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

cin >> a[i][j];

}

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

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

cin >> b[i][j];

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

}

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

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

cin >> c[i][j];

}

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

for( int j=0 ; j<n ; j++,d[i][j]=0 ){

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

d[i][j] += a[i][k] * c[k][j];

}

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

}

Тесты:

n	A	B	C	Output
3	1 2 3 4 5 6 7 8 9	0 1 0 0 0 0 0 0 0	1 0 0 0 1 0 0 0 1	1 3 3 4 5 6 7 8 9
2	4 6 12 7	3 2 1 1	7 3 2 8	65 85 107 103
3	3 4 1 1 2 1 5 6 7	1 3 1 2 4 5 6 5 1	1 1 0 5 8 1 2 3 2	43 66 11 45 69 18 82 123 27

Related Images:

A1029

17/06/2015 by Іванов Вячеслав Володимирович

Задача о восьми мирных ладьях

Условие

Получить все расстановки [latex]8[/latex] ладей на шахматной доске, при которых ни одна ладья не угрожает другой.

Решение

Для начала, выясним, а сколько существует таких расстановок, при условии, что рассматривается стандартная шахматная доска [latex]8 \times 8[/latex].

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

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

Теперь легко видеть, что положение на доске определяется перестановкой чисел [latex]1,..,8[/latex]. Как известно, число различных перестановок длины [latex]n[/latex] — [latex]P_{n}=n![/latex]. Следовательно, всего существует [latex]8!=40320[/latex] различных расстановок ладей.

Реализация
ideone: http://ideone.com/tBySY4
Легенда: R — Rook — ладья

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

int state[8] = {0, 1, 2, 3, 4, 5, 6, 7};
int main()
{
    do{
        for(int i = 0; i < 8; i++){
            for(int j = 0; j < 8; j++)
                printf("%c ", (state[i] == j ? 'R' : '#'));
            printf("\n");
        }
        printf("\n");
    } while(next_permutation(state, state+8));
    return 0;
}

#include <cstdio>

#include <algorithm>

using namespace std;

int state[8] = {0, 1, 2, 3, 4, 5, 6, 7};

int main()

{

do{

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

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

printf("%c ", (state[i] == j ? 'R' : '#'));

printf("\n");

}

printf("\n");

} while(next_permutation(state, state+8));

return 0;

}

Детали реализации

Для получения перестановок использована функция стандартной библиотеки [latex]next\_permutation()[/latex]

В силу большого объёма выходного файла (5.5 мб) он доступен отдельно, по ссылке: https://www.dropbox.com/s/yyaz7vq08jczsnl/out?dl=0

Related Images:

А719б

17/06/2015 by Іванов Вячеслав Володимирович

Условие

Симметричные квадратные матрицы [latex]A[/latex] и [latex]B[/latex] порядка [latex]n[/latex] заданы последовательностями из [latex]\frac{n(n+1)}{2}[/latex] чисел аналогично правым треугольным матрицам. Получить в аналогичном виде матрицу [latex]A^{2}-B^{2}[/latex].

Решение

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

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

Замечание 1

Подпространство симметричных матриц незамкнуто относительно умножения: произведением двух симметричных матриц может быть несимметричная матрица.

Пример

[latex] \left(\begin{array}{ccc} 1 & 1 & 3 \\ 1 & 4 & 5 \\ 3 & 5 & 0\end{array} \right) \cdot \left( \begin{array}{ccc} 4 & 0 & 0 \\ 0 & 4 & 3 \\ 0 & 3 & 2 \end{array} \right) = \left( \begin{array}{ccc} 4 & 13 & 9 \\ 4 & 31 & 22 \\ 12 & 20 & 15 \end{array} \right)[/latex]

Замечание 2

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

Во всех дальнейших выкладках подразумевается, что матрица представлена линейным массивом из [latex]\frac{n(n+1)}{2}[/latex] элементов.

Для начала, заметим, что элемент [latex]c_{i,j}[/latex] матрицы [latex]C=A^{2}[/latex], равен скалярному произведению (как векторов в стандартном базисе) [latex]i[/latex]-ой строки матрицы [latex]A[/latex] на [latex]j[/latex]-ую её строку (в силу того, что в симметричной матрице [latex]j[/latex]-ая строка совпадает с [latex]j[/latex]-м столбцом). Следовательно, для возведения в степень симметричной матрицы необходимо и достаточно реализовать операцию скалярного перемножения двух её строк.

Тогда следует понять, как по данному представлению матрицы получить её [latex]i[/latex]-ую строку. Для удобства, выпишем имеющиеся элементы в виде полной матрицы. Заметим, что первым элементом [latex]i[/latex]-ой строки будет [latex]i[/latex]-ый элемент первой строки, и обобщим это наблюдение. Обозначим позицию текущего интересующего нас элемента [latex]i[/latex]-ой строки как [latex]j[/latex]. Если [latex]j < i[/latex], то следует выбрать [latex]i[/latex]-ый элемент [latex]j[/latex]-ой строки, иначе следует выбрать все элементы [latex]j[/latex]-ой строки, лежащие правее данного. Графически можно интерпретировать алгоритм таким образом: начиная с [latex]i[/latex]-го элемента первой строки, спускаться вертикально вниз по матрице до тех пор, пока не будет достигнута [latex]i[/latex]-ая строка, далее — двигаться вправо до конца строки. Наглядность алгоритма позволяет легко воплотить его программно.
Следует только пронаблюдать, как изменяются расстояния между элементами, лежащими один под другим, при движении вниз по строкам матрицы, что позволит легко перенести алгоритм на линейное представление верхней треугольной матрицы. Предлагаем читателю самому проделать это несложное, но наглядное упражнение, для лучшего понимания алгоритма.

Теперь можно перейти непосредственно к реализации.

Тесты

[latex]n[/latex]	[latex]A[/latex]	[latex]B[/latex]	[latex]A^{2}-B^{2}[/latex]
2	1 2 5	7 4 8	-60 -48 -51
4	1 7 3 -2 3 1 9 2 8 11	4 5 11 -3 4 -7 22 1 4 0	-108 116 -8 -79 -434 -10 75 -109 290 -239

Реализация

ideone: http://ideone.com/Dyte8l

#include <bits/stdc++.h>
using namespace std;

//Симметричная квадратная матрица порядка n задана линейным набором из
//n(n+1)/2 элементов. Все методы класса оперируют только с таким представлением.

template <typename T>
class symmetric_matrix{
private:
    T* data;
    int data_size;
   
public:
    //Конструкторы.
    symmetric_matrix(){}
    symmetric_matrix(int n){
        data = new T[(n*(n+1))/2];
        data_size = n;
    }
    symmetric_matrix(int n, int value){
        data = new T[(n*(n+1))/2];
        for(int i = 0; i < (n*(n+1))/2; i++)
            data[i] = value;
        data_size = n;
    }
    //Методы.
    int size(){ return data_size; }
    T get(int pos){ return data[pos]; }
    void set(int pos, T value){ data[pos] = value; }
    //Подпространство симметричных квадратные матриц заданного порядка
    //не замкнутно относительно операции матричного умножения.
    //Тем не менее, при возведение матрицы в степень замкнутость не
    //нарушается, в связи с чем операция умножения реализована для него.
    symmetric_matrix<T> operator *(symmetric_matrix<T> B){
        int n = data_size;
        symmetric_matrix<T> C(n);
        int curr = 0;
        for(int row = 0; row < n; row++){			//row
            for(int col = row; col < n; col++){		//col
                int rpos = row, cpos = col;	        //(row, col)
                int rstep = n-1, cstep = n-1;	    //row, col step
                for(int i = 0; i < n; i++){
                    C.set(curr, C[curr] + data[rpos]*B[cpos]);
                    rpos += (rstep >= n-row)*(rstep - 1) + 1;
                    cpos += (cstep >= n-col)*(cstep - 1) + 1;
                    rstep--, cstep--;
                }
                curr++;
            }
        }
        return C;
    }

    //Операторы.
    T operator [](int pos){return data[pos];}
    symmetric_matrix<T> operator +(symmetric_matrix<T> B){
        int n = B.size();
        symmetric_matrix<T> C(n);
        for(int i = 0; i < (n*(n+1))/2; i++)
            C.set(i, data[i] + B[i]);
        return C;
    };
    symmetric_matrix<T> operator -(symmetric_matrix<T> B){
        int n = B.size();
        symmetric_matrix<T> C(n);
        for(int i = 0; i < (n*(n+1))/2; i++)
            C.set(i, data[i] - B[i]);
        return C;
    };
};

//Бинарный алгоритм возведения матрицы в степень.
template <typename T>
symmetric_matrix<T> power(symmetric_matrix<T> A, int n){
    symmetric_matrix<T> result(A.size());
    //Изначально result - нейтральный элемент относительно умножения
    //т.е. единичная матрица.
    for(int i = 0, diag = 0; i < A.size(); i++){
        result.set(diag, 1);
        diag += A.size()-i;
    }
    while(n){
        if(n & 1)
            result = result * A;
        A = A * A;
        n >>= 1;
    }
    return result;
}


int main(){
	int n; cin >> n;
	symmetric_matrix<int> A(n), B(n), C(n);
	//Считывание данных
	for(int i = 0; i < (n*(n+1))/2; i++){
        int value; cin >> value;
        A.set(i, value);
    }
    for(int i = 0; i < (n*(n+1))/2; i++){
        int value; cin >> value;
        B.set(i, value);
    }

    C = power(A, 2) - power(B, 2);
    for(int i = 0; i < (n*(n+1))/2; i++){
        cout << C.get(i) << " ";
    }
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

#include <bits/stdc++.h>

using namespace std;

//Симметричная квадратная матрица порядка n задана линейным набором из

//n(n+1)/2 элементов. Все методы класса оперируют только с таким представлением.

template <typename T>

class symmetric_matrix{

private:

T* data;

int data_size;

public:

//Конструкторы.

symmetric_matrix(){}

symmetric_matrix(int n){

data = new T[(n*(n+1))/2];

data_size = n;

}

symmetric_matrix(int n, int value){

data = new T[(n*(n+1))/2];

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

data[i] = value;

data_size = n;

}

//Методы.

int size(){ return data_size; }

T get(int pos){ return data[pos]; }

void set(int pos, T value){ data[pos] = value; }

//Подпространство симметричных квадратные матриц заданного порядка

//не замкнутно относительно операции матричного умножения.

//Тем не менее, при возведение матрицы в степень замкнутость не

//нарушается, в связи с чем операция умножения реализована для него.

symmetric_matrix<T> operator *(symmetric_matrix<T> B){

int n = data_size;

symmetric_matrix<T> C(n);

int curr = 0;

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

for(int col = row; col < n; col++){ //col

int rpos = row, cpos = col; //(row, col)

int rstep = n-1, cstep = n-1; //row, col step

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

C.set(curr, C[curr] + data[rpos]*B[cpos]);

rpos += (rstep >= n-row)*(rstep - 1) + 1;

cpos += (cstep >= n-col)*(cstep - 1) + 1;

rstep--, cstep--;

}

curr++;

}

return C;

}

//Операторы.

T operator [](int pos){return data[pos];}

symmetric_matrix<T> operator +(symmetric_matrix<T> B){

int n = B.size();

symmetric_matrix<T> C(n);

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

C.set(i, data[i] + B[i]);

return C;

};

symmetric_matrix<T> operator -(symmetric_matrix<T> B){

int n = B.size();

symmetric_matrix<T> C(n);

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

C.set(i, data[i] - B[i]);

return C;

};

//Бинарный алгоритм возведения матрицы в степень.

template <typename T>

symmetric_matrix<T> power(symmetric_matrix<T> A, int n){

symmetric_matrix<T> result(A.size());

//Изначально result - нейтральный элемент относительно умножения

//т.е. единичная матрица.

for(int i = 0, diag = 0; i < A.size(); i++){

result.set(diag, 1);

diag += A.size()-i;

}

while(n){

if(n & 1)

result = result * A;

A = A * A;

n >>= 1;

}

return result;

}

int main(){

int n; cin >> n;

symmetric_matrix<int> A(n), B(n), C(n);

//Считывание данных

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

int value; cin >> value;

A.set(i, value);

}

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

int value; cin >> value;

B.set(i, value);

}

C = power(A, 2) - power(B, 2);

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

cout << C.get(i) << " ";

}

return 0;

}

Тесты

Детали реализации

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

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

Related Images:

А712

16/06/2015 by Байков Дмитро

Задача

Дана квадратная матрица [latex]A[/latex] порядка [latex]n[/latex]. Получить матрицы [latex]\frac{1}{2}(A+A^{*}) (1)[/latex] и [latex]\frac{1}{2}(A-A^{*}) (2)[/latex].

Тесты:

Ввод	Вывод (1)	Вывод (2)
3 1 2 3 2 4 6 1 4 8	1 2 2 2 4 5 2 5 8	0 0 1 0 0 1 -1 -1 0

Код:

    #include <iostream>
    using namespace std;
     
    int main() 
    {
	    int n;
	    cin >> n;
	    double a[n][n], result1[n][n], result2[n][n];
	    for (int i = 0; i < n; i++)
	    {
			for (int j = 0; j < n; j++)
			{
				cin >> a[i][j];
			}
	    }
	    for (int i = 0; i < n; i ++)
	    {
	    	for (int j = 0; j < n; j ++)
	    	{
	    		result1[i][j] = 0.5 * ( a[i][j] + a[j][i] );
	    		result2[i][j] = 0.5 * ( a[i][j] - a[j][i] );
	    	}
	    }
	     for (int i = 0; i < n; i++)
	     {
		     for (int j = 0; j < n; j++)
		     {
			     cout << result1[i][j] << ' ';
		     }
		     cout << endl;
	     }
	     cout << endl;
	     for (int i = 0; i < n; i ++)
	     {
		     for (int j = 0; j < n; j ++)
		     {
			     cout << result2[i][j] << ' ';
		     }
		     cout << endl;
	     }
		return 0;
}

#include <iostream>

using namespace std;

int main()

{

int n;

cin >> n;

double a[n][n], result1[n][n], result2[n][n];

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

{

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

{

cin >> a[i][j];

}

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

{

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

{

result1[i][j] = 0.5 * ( a[i][j] + a[j][i] );

result2[i][j] = 0.5 * ( a[i][j] - a[j][i] );

}

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

{

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

{

cout << result1[i][j] << ' ';

}

cout << endl;

}

cout << endl;

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

{

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

{

cout << result2[i][j] << ' ';

}

cout << endl;

}

return 0;

}

Ссылка на ideone.

Сначала, вводим размер матрицы и саму матрицу, сразу же транспонируем ее. Теперь каждый элемент обычной матрицы прибавляем к транспонированному и отнимаем от транспонированного в последствии умножая на [latex]\frac{1}{2}[/latex]. Записываем это в две различные матрицы с результатом и выводим их на экран.

Код на Java

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

class Matrix
{
	public static void main (String[] args) throws java.lang.Exception
	{
	    Scanner in = new Scanner(System.in);
		int n = in.nextInt();
	    double[][] a = new double[n][n], result1 = new double[n][n], result2 = new double[n][n];
	    for (int i = 0; i < a.length; i++)
	    {
			for (int j = 0; j < a[i].length; j++)
			{
				a[i][j] = in.nextDouble();
			}
	    }
	    for (int i = 0; i < a.length; i ++)
	    {
	    	for (int j = 0; j < a[i].length; j ++)
	    	{
	    		result1[i][j] = 0.5 * (a[i][j] + a[j][i]);
	    		result2[i][j] = 0.5 * (a[i][j] - a[j][i]);
	    	}
	    }
	     for (int i = 0; i < a.length; i++)
	     {
		     for (int j = 0; j < a[i].length; j++)
		     {
				System.out.print(result1[i][j] + " ");
		     }
		     System.out.println(' ');
	     }
	    System.out.println(' ');
	    for (int i = 0; i < a.length; i ++)
	     {
		     for (int j = 0; j < a[i].length; j ++)
		     {
			    System.out.print(result2[i][j] + " ");
		     }
		     System.out.println(' ');
	     }
	}
}