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

21/11/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]

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

import java.util.Scanner;
 
public class Main {
	public static void main (String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int [][] s = new int[50][50];
		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(true)
		{
			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++)
			{
			    System.out.print(s[i][j]);
			}
			System.out.println();
		}
	}
}

import java.util.Scanner;

public class Main {

public static void main (String[] args) {

Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt();

int [][] s = new int[50][50];

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(true)

{

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++)

{

System.out.print(s[i][j]);

}

System.out.println();

}

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

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

Ссылки

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

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

13/11/2018 by Александр Дяченко

Задача

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

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

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

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

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

Тесты

Входные данные	Выходные данные
4 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 3 2	1 2 5 6 9 1
5 18 25 34 44 -43 54 65 75 85 -32 95 15 25 35 -3 -4 15 -6 37 0 44 43 23 3 -12 4 3	18 25 34 54 65 75 95 15 25 -4 15 -6
6 30 -10 30 -69 -84 75 -3 -39 60 15 75 -74 36 68 35 23 25 -44 16 42 83 15 59 -18 71 43 35 -81 -38 51 37 -49 55 26 6 33 4 5	30 -10 30 -69 -84 -3 -39 60 15 75 36 68 35 23 25 16 42 83 15 59

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

import java.io.*;
import java.util.*;
 
public class Main
{
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
 
		int n = in.nextInt();
		int [][] x = new int [n][n];
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				x[i][j] = in.nextInt();
		int r = in.nextInt();
		int c = in.nextInt();
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++)
				out.print(x[i][j] + " ");
			out.print("\n");
		}
 
		out.flush();
	}
}

import java.io.*;

import java.util.*;

public class Main

{

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

PrintWriter out = new PrintWriter(System.out);

int n = in.nextInt();

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

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

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

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

int r = in.nextInt();

int c = in.nextInt();

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

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

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

out.print("\n");

}

out.flush();

}

Решение

Для того, чтобы вывести матрицу на экран, нам нужно запустить $2$ цикла, один из которых будет вложен в предыдущий:

первый цикл ($17$ строка кода) будет отвечать за количество выводимых строк матрицы — по условию, нужно вывести первые $r$ строк;
второй цикл ($18$ строка кода) будет отвечать за количество выводимых столбцов матрицы — по условию, нужно вывести первые $c$ столбцов.

Ссылки

Условие задачи на e-olymp
Код решения на Ideone
Решение этой же задачи на C++

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

15/10/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$

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
public class Main{

    private static class Node {
        private int i;
        private int j;

        private Node(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }
    private static void fill(int[][] a, int value) {
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[i].length; j++) {
                a[i][j] = value;
            }
        }
    }

    private static void bfsSecondPlayer(char[][] map, int[][] moves, Node start) {
        Queue<Node> queue = new LinkedList<>();
        moves[start.i][start.j] = 0;
        queue.add(start);
        while (!queue.isEmpty()) {
            Node curNode = queue.poll();
            int i = curNode.i;
            int j = curNode.j;
            if (i > 0 && map[i - 1][j] != 'R' && map[i - 1][j] != 'e' && moves[i][j] + 1 < moves[i - 1][j]) {
                moves[i - 1][j] = moves[i][j] + 1;
                queue.add(new Node(i - 1, j));
            }
            if (i < moves.length - 1 && map[i + 1][j] != 'R' && map[i + 1][j] != 'e' && moves[i][j] + 1 < moves[i + 1][j]) {
                moves[i + 1][j] = moves[i][j] + 1;
                queue.add(new Node(i + 1, j));
            }
            if (j > 0 && map[i][j - 1] != 'R' && map[i][j - 1] != 'e' && moves[i][j] + 1 < moves[i][j - 1]) {
                moves[i][j - 1] = moves[i][j] + 1;
                queue.add(new Node(i, j - 1));
            }
            if (i < moves[0].length - 1 && map[i][j + 1] != 'R' && map[i][j + 1] != 'e' && moves[i][j] + 1 < moves[i][j + 1]) {
                moves[i][j + 1] = moves[i][j] + 1;
                queue.add(new Node(i, j + 1));
            }
        }
    }

    private static boolean bfsFirstPlayer(char[][] map, int[][] moves, int[][] secondPlayerMoves, Node start) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(start);
        moves[start.i][start.j] = 0;
        while (!queue.isEmpty()) {
            Node curNode = queue.poll();
            int i = curNode.i;
            int j = curNode.j;
            if (map[i][j] == 'e') {
                return true;
            }
            if (i > 0 && map[i - 1][j] != 'R' && moves[i][j] + 1 < Math.min(moves[i - 1][j], secondPlayerMoves[i - 1][j])) {
                moves[i - 1][j] = moves[i][j] + 1;
                queue.add(new Node(i - 1, j));
            }
            if (i < moves.length - 1 && map[i + 1][j] != 'R' && moves[i][j] + 1 < Math.min(moves[i + 1][j], secondPlayerMoves[i + 1][j])) {
                moves[i + 1][j] = moves[i][j] + 1;
                queue.add(new Node(i + 1, j));
            }
            if (j > 0 && map[i][j - 1] != 'R' && moves[i][j] + 1 < Math.min(moves[i][j - 1], secondPlayerMoves[i][j - 1])) {
                moves[i][j - 1] = moves[i][j] + 1;
                queue.add(new Node(i, j - 1));
            }
            if (i < moves[0].length - 1 && map[i][j + 1] != 'R' && moves[i][j] + 1 < Math.min(moves[i][j + 1], secondPlayerMoves[i][j + 1])) {
                moves[i][j + 1] = moves[i][j] + 1;
                queue.add(new Node(i, j + 1));
            }
        }
        return false;
    }

    public static void main(String[] args) throws IOException{
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int tests = Integer.parseInt(bufferedReader.readLine());
        for (int r = 0; r < tests; r++) {
            String[] sizes = bufferedReader.readLine().split(" ");
            int n = Integer.parseInt(sizes[0]);
            int m = Integer.parseInt(sizes[1]);
            char[][] map = new char[n][m];
            Node g = null;
            Node l = null;
            Node e = null;
            for (int i = 0; i < n; i++) {
                map[i] = bufferedReader.readLine().toCharArray();
                for (int j = 0; j < m; j++) {
                    if (map[i][j] == 'g') {
                        g = new Node(i, j);
                    }
                    else if (map[i][j] == 'l') {
                        l = new Node(i, j);
                    }
                    else if (map[i][j] == 'e') {
                        e = new Node(i, j);
                    }
                }
            }
            int[][] secondPlayerDistances = new int[n][m];
            fill(secondPlayerDistances, Integer.MAX_VALUE);
            bfsSecondPlayer(map, secondPlayerDistances, l);
            int[][] firstPlayerDistances = new int[n][m];
            fill(firstPlayerDistances, Integer.MAX_VALUE);
            boolean ok = bfsFirstPlayer(map, firstPlayerDistances, secondPlayerDistances, g);
            System.out.println(ok ? "YES" : "NO");
        }
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.LinkedList;

import java.util.Queue;

public class Main{

private static class Node {

private int i;

private int j;

private Node(int i, int j) {

this.i = i;

this.j = j;

}

private static void fill(int[][] a, int value) {

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

for (int j = 0; j < a[i].length; j++) {

a[i][j] = value;

}

private static void bfsSecondPlayer(char[][] map, int[][] moves, Node start) {

Queue<Node> queue = new LinkedList<>();

moves[start.i][start.j] = 0;

queue.add(start);

while (!queue.isEmpty()) {

Node curNode = queue.poll();

int i = curNode.i;

int j = curNode.j;

if (i > 0 && map[i - 1][j] != 'R' && map[i - 1][j] != 'e' && moves[i][j] + 1 < moves[i - 1][j]) {

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

queue.add(new Node(i - 1, j));

}

if (i < moves.length - 1 && map[i + 1][j] != 'R' && map[i + 1][j] != 'e' && moves[i][j] + 1 < moves[i + 1][j]) {

moves[i + 1][j] = moves[i][j] + 1;

queue.add(new Node(i + 1, j));

}

if (j > 0 && map[i][j - 1] != 'R' && map[i][j - 1] != 'e' && moves[i][j] + 1 < moves[i][j - 1]) {

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

queue.add(new Node(i, j - 1));

}

if (i < moves[0].length - 1 && map[i][j + 1] != 'R' && map[i][j + 1] != 'e' && moves[i][j] + 1 < moves[i][j + 1]) {

moves[i][j + 1] = moves[i][j] + 1;

queue.add(new Node(i, j + 1));

}

private static boolean bfsFirstPlayer(char[][] map, int[][] moves, int[][] secondPlayerMoves, Node start) {

Queue<Node> queue = new LinkedList<>();

queue.add(start);

moves[start.i][start.j] = 0;

while (!queue.isEmpty()) {

Node curNode = queue.poll();

int i = curNode.i;

int j = curNode.j;

if (map[i][j] == 'e') {

return true;

}

if (i > 0 && map[i - 1][j] != 'R' && moves[i][j] + 1 < Math.min(moves[i - 1][j], secondPlayerMoves[i - 1][j])) {

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

queue.add(new Node(i - 1, j));

}

if (i < moves.length - 1 && map[i + 1][j] != 'R' && moves[i][j] + 1 < Math.min(moves[i + 1][j], secondPlayerMoves[i + 1][j])) {

moves[i + 1][j] = moves[i][j] + 1;

queue.add(new Node(i + 1, j));

}

if (j > 0 && map[i][j - 1] != 'R' && moves[i][j] + 1 < Math.min(moves[i][j - 1], secondPlayerMoves[i][j - 1])) {

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

queue.add(new Node(i, j - 1));

}

if (i < moves[0].length - 1 && map[i][j + 1] != 'R' && moves[i][j] + 1 < Math.min(moves[i][j + 1], secondPlayerMoves[i][j + 1])) {

moves[i][j + 1] = moves[i][j] + 1;

queue.add(new Node(i, j + 1));

}

return false;

}

public static void main(String[] args) throws IOException{

BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

int tests = Integer.parseInt(bufferedReader.readLine());

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

String[] sizes = bufferedReader.readLine().split(" ");

int n = Integer.parseInt(sizes[0]);

int m = Integer.parseInt(sizes[1]);

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

Node g = null;

Node l = null;

Node e = null;

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

map[i] = bufferedReader.readLine().toCharArray();

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

if (map[i][j] == 'g') {

g = new Node(i, j);

}

else if (map[i][j] == 'l') {

l = new Node(i, j);

}

else if (map[i][j] == 'e') {

e = new Node(i, j);

}

int[][] secondPlayerDistances = new int[n][m];

fill(secondPlayerDistances, Integer.MAX_VALUE);

bfsSecondPlayer(map, secondPlayerDistances, l);

int[][] firstPlayerDistances = new int[n][m];

fill(firstPlayerDistances, Integer.MAX_VALUE);

boolean ok = bfsFirstPlayer(map, firstPlayerDistances, secondPlayerDistances, g);

System.out.println(ok ? "YES" : "NO");

}

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

Представим карту острова в виде неориентированного графа, вершинами которого в случае Гайбраша являются все участки, кроме участков с пометкой «R», а для Ли Чака — все участки, кроме участков с пометками «R» и «e». Две вершины будут соединяться ребром, если они соответствуют участкам, имеющим общую сторону. Обозначим начальное местоположение Гайбраша — $g,$ Ли Чака — $l.$, выход $e.$
Безопасный для Гайбраша маршрут существует тогда и только тогда, когда существует путь $\omega,$ такой, что для $\forall v \in \omega \ \rho \left(g, v \right ) + 1 < \rho(l, v).$ С помощью поиска в ширину найдем минимальное количество шагов, за которое Ли Чак попадает в каждую клетку, в которую он может попасть. Аналогично реализуем поиск в ширину для Гайбраша с той лишь разницей, что Гайбраш должен миновать те вершины графа, в которые он будет добираться дольше, чем Ли Чак. Если при этом найдется путь, соединяющий вершину, соответствующую начальному местоположению Гайбраша с вершиной, соответствующую цели, то он сможет спастись, в противном случае — нет.

Ссылки

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

A393a

28/11/2017 by Мазурин Эдвард

Задача:

Даны натуральное число [latex]n[/latex], целочисленная квадратная матрица порядка [latex]n[/latex]. Получить [latex]{b}_{1}[/latex],…,[latex]{b}_{n},[/latex] где [latex]{b}_{i}[/latex] — это наименьшее из значений, элементов находящихся в начале [latex]i[/latex]-й строки матрицы до элемента, принадлежащего главной диагонали, включительно.

Тесты:


Вводимые данные		Предполагаемый вывод	Комментарий
4	4 3 2 1	4 3 2 1	Тест пройден
	4 3 2 1
	4 3 2 1
	4 3 2 1
	1 2 3 4	1 1 1 1	Тест пройден
	1 2 3 4
	1 2 3 4
	1 2 3 4

Решение:

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

Код:

import java.util.*;

public class multi_arrays {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        System.out.print("Введите n: ");
        int n = in.nextInt();                //Объявление переменной, обозначающей размерность массива
            int[][] a = new int [n][n];      //Создание двумерного массива
        for (int i = 0; i < n; i++) {        
            for (int j = 0; j < n; j++) {
                System.out.print("Заполните массивы элементами: ");
                a[i][j] = in.nextInt();
            }
        }
        for (int i = 0; i < n; i++) {
            int min = a[i][0];
            for (int j = 0; i - j >= 0; j++)  // критерий отбора элементов под главной диагональю
            {
                if (a[i][j] < min) {
                    min = a[i][j];
                }
            }
            System.out.println(min);
        }
    }
}

import java.util.*;

public class multi_arrays {

public static void main(String[] args){

Scanner in = new Scanner(System.in);

System.out.print("Введите n: ");

int n = in.nextInt(); //Объявление переменной, обозначающей размерность массива

int[][] a = new int [n][n]; //Создание двумерного массива

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

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

System.out.print("Заполните массивы элементами: ");

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

}

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

int min = a[i][0];

for (int j = 0; i - j >= 0; j++) // критерий отбора элементов под главной диагональю

{

if (a[i][j] < min) {

min = a[i][j];

}

System.out.println(min);

}

Версия программы на Ideone.com

Ссылка на источник

Ю4.32

03/07/2017 by Хоба Юрий

Постановка задачи

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

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

[latex]n[/latex] — размерность матрицы [latex](n\geq 1)[/latex].
[latex]A[/latex] — квадратная матрица.

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

Суммы элементов матрицы [latex]A[/latex] по каждой из линий, параллельной главной диагонали.

Тесты

№	Входные данные		Выходные данные
№	Размерность матрицы [latex](n)[/latex]	Матрица [latex]A[/latex]	Суммы
1	2	[latex]\begin{pmatrix} 3 & 6\\ -7 & -5 \end{pmatrix} [/latex]	-7 -2 6
2	3	[latex]\begin{pmatrix} 1 & 2 & 3\\ 4 & 5 & 6\\ 7 & 8 & 9 \end{pmatrix} [/latex]	7 12 15 8 3
3	4	[latex]\begin{pmatrix} 4 & 1 & -6 & 3\\ 2 & 8 & 19 & 7\\ -8 & -11 & 3 & -13\\ 0 & 2 & 16 & -9 \end{pmatrix} [/latex]	0 -6 7 6 7 1 3

Посмотреть работу программы на примере третьего теста можно на сайте ideone.

Решение

import java.util.*;

class task5
{	
	public static void main (String[] args)
	{
		int n;
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		if (n<1)
		{
			System.out.println("Размерность матрицы не может быть меньше 1.");
			return;
		}

		double[][] matrix = new double[n][n];
		double[] sum = new double [2*n - 1];
		
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				matrix[i][j] = in.nextDouble();
		
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				 sum[(j-i + n-1] += matrix[i][j];
		
		for (int i=0; i<(2*n-1); i++)
			System.out.print(sum[i]+" ");
		
	}
}

import java.util.*;

class task5

{

public static void main (String[] args)

{

int n;

Scanner in = new Scanner(System.in);

n = in.nextInt();

if (n<1)

{

System.out.println("Размерность матрицы не может быть меньше 1.");

return;

}

double[][] matrix = new double[n][n];

double[] sum = new double [2*n - 1];

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

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

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

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

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

sum[(j-i + n-1] += matrix[i][j];

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

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

}

Описание решения

Сначала объявляем переменную n — размерность матрицы [latex]A[/latex] — и присваиваем ей значение, которое вводит пользователь. Если [latex](n\geq 1)[/latex] — продолжаем работу, иначе выводим сообщение об ошибке и завершаем работу программы.

Теперь, зная размерность матрицы, можем инициализировать 2 массива:

Двумерный массив double[][] matrix = new double[n][n]; размерностью [latex](n\times n)[/latex], который будет содержать в себе значения элементов матрицы [latex]A[/latex];
Массив double[] sum = new double [2*n - 1]; размерностью [latex](2*n-1)[/latex] для хранения сумм диагоналей. Такая размерность обусловлена следующей логикой: главная диагональ матрицы размерностью [latex](n\times n)[/latex] содержит [latex]n[/latex] элементов. Побочная диагональ, находящаяся выше, содержит в себе уже [latex](n-1)[/latex] элементов и т.д., пока элементов в диагонали больше нуля. Становится ясно, что выше главной диагонали находится [latex](n-1)[/latex] побочных диагоналей, еще столько же ниже. Прибавляем еще главную диагональ к этому числу и выводим формулу количества диагоналей у матрицы, параллельных главной: [latex]2(n-1)+1=2n-1[/latex].

Заполняем с помощью двух циклов for массив matrix из потока ввода, а затем в таких же циклах находим суммы элементов требуемых диагоналей ( sum[(j-i) + (n-1)] += matrix[i][j];).

Известно, что индексы [latex]i,j[/latex] элементов главной диагонали матрицы всегда одинаковы. Аналогично можно заметить, что на побочных диагоналях индекс [latex]j[/latex] отличается от индекса [latex]i[/latex] на число — «расстояние» между главной диагональю и рассматриваемой побочной. К примеру, если рассматривать побочную диагональ, находящуюся выше через одну от главной («расстояние» между ними равно 2), то в таком случае [latex]j-i=2[/latex].

И если на главной диагонали разность индексов будет равна 0, на диагоналях выше эта разность будет числом положительным, а на диагоналях ниже — отрицательным, то при попытке обращения к элементу массива sum[j-i] мы неизбежно столкнемся с ошибкой, так как индекс массива не может быть числом отрицательным. Значит, чтобы избежать этого, нам надо прибавить к этому индексу некую константу, чтобы самая нижняя диагональ [latex]n-1[/latex] обладала индексом 0 в массиве sum. Отсюда и формула [latex](j-i+n-1)[/latex].

Ю 4.9

30/06/2017 by Шостак Дмитрий

Задача

В матрице [latex]A(n, m) [/latex] все ненулевые элементы заменить обратными по величине и противоположными по знаку.

Тесты

№	n	m	Входная матрица	Выходная матрица
1	3	3	6 -2 -1 0 0 4 11 2 -3	-0.167 0.500 1.000 0.000 0.000 -0.250 -0.091 -0.500 0.333
2	3	4	-3 -9 15 12 -31 -8 2 8 -1 2 -6 -8	0.333 0.111 -0.067 -0.083 0.032 0.125 -0.500 -0.125 1.000 -0.500 0.167 0.125
3	4	3	1 1 1 1 1 1 1 1 1 1 1 1	-1.000 -1.000 -1.000 -1.000 -1.000 -1.000 -1.000 -1.000 -1.000 -1.000 -1.000 -1.000

Решение

class FifthLab
{
	public static void main (String[] args)
	{
		Scanner input = new Scanner(System.in);
		int n, m;
		
		n = input.nextInt();
		m = input.nextInt();
		
		double[][] A = new double[n][m];
		
		for(int i = 0; i < n; i++)
		{
			for(int j = 0; j < m; j++)
			{
				A[i][j] = input.nextDouble();
			}
		}
		
		for(int i = 0; i < n; i++)
		{
			for(int j = 0; j < m; j++)
			{
				if(A[i][j] != 0)
				{
					A[i][j] = -(1/A[i][j]);
				}
			}
		}
		
		for(int i = 0; i < n; i++)
		{
			for(int j = 0; j < m; j++)
			{
				System.out.printf("%.3f ",A[i][j]);
			}
			System.out.println();
		}
	}
}

class FifthLab

{

public static void main (String[] args)

{

Scanner input = new Scanner(System.in);

int n, m;

n = input.nextInt();

m = input.nextInt();

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

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

{

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

{

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

}

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

{

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

{

if(A[i][j] != 0)

{

A[i][j] = -(1/A[i][j]);

}

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

{

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

{

System.out.printf("%.3f ",A[i][j]);

}

System.out.println();

}

Проверить работу кода можно в облаке по ссылке — Ideone.

Пояснения

Объявляем и инициализируем переменные n и m , которые являются размерами нашей матрицы [latex]A[/latex]. Объявляем нашу матрицу и создаем экземпляр с размерами [latex]n[/latex] x [latex]m[/latex]. Далее создаем цикл по i от 0 до [latex]n-1[/latex] в котором создаем вложенный цикл по j от 0 до [latex]m-1[/latex], и в нем поэлементно вводим значения матрицы. В следующем цикле снова создаем вложенный, в котором мы проходим по каждому элементу матрицы и проверяем не равен ли он нулю if(A[i][j] != 0) . Если условие выполняется, то мы заменяем элемент на обратный и меняем знак. В последнем цикле выводим полученную матрицу, элементы которой будут выводится с точностью до трех символов после запятой.

А694а. Многомерные массивы

28/05/2017 by Anh Tuan

Условие
Получить квадратную матрицу порядка $latex \begin{pmatrix}1 &0 &\cdots & 0 \\ 0 & 1 &\cdots &0 \\ \cdots &\cdots &\cdots \cdots & \cdots \\ 0 & 0 & \cdots & 1\end{pmatrix}$

Тесты

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

import java.util.Scanner;
public class Lab6
{
    public static void main(String[] args) 
    {
        int n;
        Scanner scanIn = new Scanner(System.in);        
        n = scanIn.nextInt();
        int[][] m = new int[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++) 
            {
                System.out.println(m[i][y] + " ");
            }
            System.out.println("\n");
        }
    }   
}

import java.util.Scanner;

public class Lab6

{

public static void main(String[] args)

{

int n;

Scanner scanIn = new Scanner(System.in);

n = scanIn.nextInt();

int[][] m = new int[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++)

{

System.out.println(m[i][y] + " ");

}

System.out.println("\n");

}

Решение

С помощью цикла заполняем главную диагональ единицами.
Приравниваем элементы не равные единице к нулю.
Вывод массива.

Iseone.com

А702а

23/11/2016 by Коваль Максим

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

1	2
3	4

0.666667

1.66667

Пройдено

5	6
7	8

2.66667

3.66667

Пройдено

Исходный код:

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main {
      public static void main(String[] args) {
           Scanner in = new Scanner(System.in);
           int n = in.nextInt();
           double[][] a = new double[n][n];
           double[]res = new double[n];
           for( int i=0 ; i<n ; i++ ){
                res[i] = 0;
           }
           for( int j=0 ; j<n ; j++ ){
                for( int i=0 ; i<n ; i++ ){
                a[i][j] = in.nextInt();
                res[j] += a[i][j]*(1.0/((i+1)*(i+1)+2));
                } 
           System.out.println("res["+j+"] ="+res[j]);
           }
     }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int n = in.nextInt();

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

double[]res = new double[n];

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

res[i] = 0;

}

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

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

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

res[j] += a[i][j]*(1.0/((i+1)*(i+1)+2));

}

System.out.println("res["+j+"] ="+res[j]);

}

Ссылка на Ideone

http://ideone.com/UAvHF4

e-olymp 974. Флойд-1

01/11/2016 by Эдуард Брагар

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

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

В первой строке записано количество вершин графа n (1 ≤ [latex]n[/latex] ≤ 100). В следующих n строках записано по [latex]n[/latex] чисел — матрица смежности графа ([latex]j[/latex]-ое число в [latex]i[/latex]-ой строке соответствует весу ребра из вершины [latex]i[/latex] в вершину [latex]j[/latex]). Все числа по модулю не превышают 100. На главной диагонали матрицы — всегда нули.

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

Выведите [latex]n[/latex] строк по [latex]n[/latex] чисел — матрицу кратчайших расстояний между парами вершин. [latex]j[/latex]-ое число в [latex]i[/latex]-ой строке должно равняться весу кратчайшего пути из вершины [latex]i[/latex] в вершину [latex]j[/latex].

Алгоритм

(взято с Википедии)

Пусть вершины графа [latex]{\displaystyle G=(V,\;E),\;|V|=n}[/latex] пронумерованы от 1 до [latex] {\displaystyle n}[/latex] и введено обозначение [latex]{\displaystyle d_{ij}^{k}}[/latex] для длины кратчайшего пути от [latex] {\displaystyle i}[/latex] до [latex]{\displaystyle j}[/latex], который кроме самих вершин [latex] {\displaystyle i,\;j} [/latex] проходит только через вершины [latex]{\displaystyle 1\ldots k} [/latex]. Очевидно, что [latex]{\displaystyle d_{ij}^{0}} [/latex] — длина (вес) ребра [latex]{\displaystyle (i,\;j)}[/latex], если таковое существует (в противном случае его длина может быть обозначена как [latex]{\displaystyle \infty } [/latex] ).

Существует два варианта значения [latex] {\displaystyle d_{ij}^{k},\;k\in \mathbb {(} 1,\;\ldots ,\;n)} d_{ij}^{k},\;k\in \mathbb {(} 1,\;\ldots ,\;n)[/latex]:

Кратчайший путь между [latex]{\displaystyle i,\;j}[/latex] не проходит через вершину [latex] {\displaystyle k}[/latex], тогда [latex]{\displaystyle d_{ij}^{k}=d_{ij}^{k-1}}[/latex] Существует более короткий путь между [latex]{\displaystyle i,\;j}[/latex], проходящий через [latex]{\displaystyle k}[/latex], тогда он сначала идёт от [latex]{\displaystyle i} [/latex] до [latex] {\displaystyle k} [/latex], а потом от [latex] {\displaystyle k} [/latex] до [latex] {\displaystyle j} [/latex]. В этом случае, очевидно, [latex]{\displaystyle d_{ij}^{k}=d_{ik}^{k-1}+d_{kj}^{k-1}}[/latex]

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

Тогда рекуррентная формула для [latex]{\displaystyle d_{ij}^{k}}[/latex] имеет вид:

[latex]{\displaystyle d_{ij}^{0}}[/latex] — длина ребра [latex] {\displaystyle (i,\;j);} (i,\;j);[/latex] [latex]{\displaystyle d_{ij}^{k}=\min(d_{ij}^{k-1},\;d_{ik}^{k-1}+d_{kj}^{k-1}).}[/latex]

Алгоритм Флойда-Уоршелла последовательно вычисляет все значения [latex]{\displaystyle d_{ij}^{k},} [/latex], [latex]{\displaystyle \forall i,\;j}[/latex] для [latex] {\displaystyle k} [/latex] от 1 до [latex] {\displaystyle n} [/latex]. Полученные значения [latex] {\displaystyle d_{ij}^{n}}[/latex] являются длинами кратчайших путей между вершинами [latex]. {\displaystyle i,\;j.} [/latex].

Код

/* package whatever; // don't place package name! */

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


class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
			Scanner in =new Scanner(System.in);
			int n = in.nextInt();
			int w[][] = new int[n][n];	 
			for( int i = 0 ; i < n ; i++ ){
				for( int j = 0 ; j < n ; j++ ){
					w[i][j] = in.nextInt();
				}
			}
	
			for( int k = 0 ; k < n ; k++ ){
				for( int i = 0 ; i<n ; i++ ){
					for( int j=0 ; j<n ; j++ ){
					    w[i][j] = Math.min(w[i][j], w[i][k] + w[k][j]);
					}
				}
			}
    
			for( int i = 0 ; i < n ; i++ ){
				for( int j = 0 ; j < n ; j++ ){
		    		System.out.print(w[i][j] + " ");
				}
				System.out.println();
    		}
	}
}

/* package whatever; // don't place package name! */

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

Scanner in =new Scanner(System.in);

int n = in.nextInt();

int w[][] = new int[n][n];

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

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

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

}

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

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

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

w[i][j] = Math.min(w[i][j], w[i][k] + w[k][j]);

}

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

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

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

}

System.out.println();

}

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

A410e

16/10/2016 by Эдуард Брагар

Дана целочисленная матрица [latex]\begin{bmatrix}a_{i,j}\end{bmatrix},i,j=1,..,n[/latex].Получить [latex]b_{1},..,b_{n}[/latex],где [latex]b_{i}[/latex] — это:

[latex]\underset{1\leq j\leq n}{\max a_{ij}}\ * \underset{1\leq j\leq n}{\min a_{ji}}[/latex]

Исходя из задачи ясно, что из данной матрицы надо взять максимальный элемент [latex]i[/latex]-й строки и умножить его на минимальный элемент [latex]i[/latex] -го столбца. Так например, если нам дана матрица 2-го порядка [latex]\begin{Vmatrix}1&2\\4&1\end{Vmatrix}[/latex] то [latex]b_{1} = 2[/latex], [latex]b_{2} = 4[/latex].

    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{
		Scanner in = new Scanner(System.in);
		int n,maxa,mina;
		n = in.nextInt();
		int a[][] = new int[n][n];
		
		for(int i = 0 ; i < n; ++i){
			for(int j = 0; j < n; ++j) {
				a[i][j] = in.nextInt();
			}
		}
		
		int b[] = new int[n];
		
		for( int i = 0; i < n; ++i ) {
		
			maxa = a[i][0]; //Придаем максимуму значение первого элемента i-й строки.
			mina = a[0][i]; //Минимуму же придаем значение первого элемента i-го столбца.
		
			for( int j = 0; j < n; ++j ) {
				maxa = (maxa > a[i][j] ? maxa : a[i][j]); //Вычисляем максимум i-й строки.
				mina = (mina < a[j][i] ? mina : a[j][i]); //Минимум i-го столбца.
			}
		
			b[i] = maxa * mina; //Наш результат.
		}	
			
		for( int i = 0; i < n; ++i ){
			System.out.print( b[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{

Scanner in = new Scanner(System.in);

int n,maxa,mina;

n = in.nextInt();

int a[][] = new int[n][n];

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

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

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

}

int b[] = new int[n];

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

maxa = a[i][0]; //Придаем максимуму значение первого элемента i-й строки.

mina = a[0][i]; //Минимуму же придаем значение первого элемента i-го столбца.

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

maxa = (maxa > a[i][j] ? maxa : a[i][j]); //Вычисляем максимум i-й строки.

mina = (mina < a[j][i] ? mina : a[j][i]); //Минимум i-го столбца.

}

b[i] = maxa * mina; //Наш результат.

}

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

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

}

Тесты

Матрица порядка [latex]n[/latex], где [latex]n[/latex]:	[latex]a[i][j][/latex]	Результат
2	[latex]\begin{Vmatrix}1&2\\4&1\end{Vmatrix}[/latex]	2 4
3	[latex]\begin{Vmatrix}1&2&3\\4&1&-6\\1&-2&-1\end{Vmatrix}[/latex]	3 -8 -6

Решение

Для нахождения максимума [latex]a_{ij}[/latex], введем переменную и будем придавать ей начальное значение 1-го элемента [latex]i[/latex]-й строки. Дабы при расчете максимума проходя по элементам строки мы не сравнивали каждый [latex]i[/latex]-й элемент с 1-м, придавать начальное значение максимуму мы будем в цикле по [latex]i[/latex]. Аналогично с минимумом [latex]a_{ij}[/latex], одно единственное но, начальное значение минимума будет равно первому элементу [latex]i[/latex]-го столбца.

http://ideone.com