e-olymp 975. Флойд

04/07/2017 by Шостак Дмитрий

Задача

Постановка задачи на e-olymp.

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

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

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

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

Вывести искомое максимальное кратчайшее расстояние.

Тесты

№	n	matrix	Результат
1	4	0 5 9 -1 -1 0 2 8 -1 -1 0 7 4 -1 -1 0	16
2	3	0 -1 2 2 0 -1 4 1 0	4
3	5	0 -1 -1 3 4 2 0 3 -1 4 -1 4 0 -1 4 3 -1 2 0 1 1 1 -1 -1 0	8

Ссылка на успешно пройденные тесты на сайте e-olymp.

Решение

import java.util.*;
public class Graph {

    public static void main(String[] args){
        Scanner input =  new Scanner(System.in);

        int n, max = 0;
        n = input.nextInt();
        int[][] matrix = new int[n][n];

        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                matrix[i][j] = input.nextInt();
            }
        }

        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                for(int k = 0; k < n; k++){
                    if(j != k && matrix[j][i] != -1 && matrix[i][k] != -1){
                        if(matrix[j][k] == -1)
                            matrix[j][k] = matrix[j][i] + matrix[i][k];
                        else
                            matrix[j][k] = Math.min(matrix[j][k], matrix[j][i] + matrix[i][k]);
                    }
                }
            }
        }

        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(matrix[i][j] > max) max = matrix[i][j];
            }
        }

        System.out.println(max);
    }
}

import java.util.*;

public class Graph {

public static void main(String[] args){

Scanner input = new Scanner(System.in);

int n, max = 0;

n = input.nextInt();

int[][] matrix = new int[n][n];

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

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

matrix[i][j] = input.nextInt();

}

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

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

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

if(j != k && matrix[j][i] != -1 && matrix[i][k] != -1){

if(matrix[j][k] == -1)

matrix[j][k] = matrix[j][i] + matrix[i][k];

else

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

}

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

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

if(matrix[i][j] > max) max = matrix[i][j];

}

System.out.println(max);

}

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

Пояснения

Данная задача решается при использовании алгоритма Флойда-Уоршелла, суть которого состоит в нахождении длин кратчайших путей между всеми парами вершин во взвешенном ориентированном графе. Код данного алгоритма можно наблюдать в цикле по [latex]i[/latex], в котором имеются два вложенных цикла по [latex]j[/latex] и по [latex]k[/latex]. Здесь мы проходим по элементам матрицы смежности графа, проверяя существует ли ребро между вершинами. Далее следуя алгоритму Флойда выполняем следующее действие — с помощью функции Math.min() находим минимальный путь из одной вершины в другую, записывая его в матрицу. По нахождении всех кратчайших путей, находим максимальный из них, и выводим его в консоль.

Класс для хранения матриц

04/07/2017 by Шостак Дмитрий

Задача

Напишите класс для хранения матриц и реализуйте основные операции работы с ними.

Тесты

№	Операция	Входная матрица А	Входная матрица В	Результат
1	Транспони-рования	33 34 12 33 19 10 12 14 17 84 24 51 43 71 21	—	33 33 12 84 43 34 19 14 24 71 12 10 17 51 21
2	Сложения	-1 1 -1 1 -1 1 -1 1 -1	1 -1 1 -1 1 -1 1 -1 1	0 0 0 0 0 0 0 0 0
3	Вычитания	-1 1 -1 1 -1 1 -1 1 -1	1 -1 1 -1 1 -1 1 -1 1	-2 2 -2 2 -2 2 -2 2 -2
4	Умножения	33 34 12 33 19 10 12 14 17 84 24 51 43 71 21	10 11 34 55 33 45 17 81 45 63 12 16	1992 2649 1844 4761 1407 1848 1565 3514 1347 1833 850 2066 3927 5217 3876 7380 3718 4991 2921 8452

Решение

class Matrix {

    int n, m;
    int[][] mainMatrix;

    public Matrix(int n, int m)
    {
        this.n = n;
        this.m = m;
        this.mainMatrix = new int[this.n][this.m];
    }

    public Matrix(int [][] paramMatrix)
    {
        this.n = paramMatrix.length;
        this.m = paramMatrix[0].length;
        this.mainMatrix = paramMatrix;
    }

    public int getElement(int n, int m)
    {
        return this.mainMatrix[n][m];
    }

    public void setElement(int n, int m, int value)
    {
        this.mainMatrix[n][m] = value;
    }

    public int getVerticalLength()
    {
        return this.mainMatrix.length;
    }

    public int getHorizontalLength()
    {
        return this.mainMatrix[0].length;
    }

    public void fillRandomValues()
    {
        Random rand = new Random();

        for(int i = 0; i < this.n; i++)
        {
            for(int j = 0; j < this.m; j++)
            {
                this.mainMatrix[i][j] = rand.nextInt(100);
            }
        }
    }

    public void displayMatrix()
    {
        for(int i = 0; i < this.n; i++)
        {
            for(int j = 0; j < this.m; j++)
            {
                System.out.print(this.mainMatrix[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static int[][] transpone(int[][] paramMatrix)
    {
        int[][] tmpMatrix = new int[paramMatrix[0].length][paramMatrix.length];
        for(int i = 0; i < paramMatrix[0].length; i++)
        {
            for(int j = 0; j < paramMatrix.length; j++)
            {
                tmpMatrix[i][j] = paramMatrix[j][i];
            }
        }
        return tmpMatrix;
    }

    public static Matrix transpone(Matrix paramMatrix)
    {
        Matrix tmpMatrix = new Matrix(paramMatrix.m, paramMatrix.n);
        for(int i = 0; i < paramMatrix.m; i++)
        {
            for(int j = 0; j < paramMatrix.n; j++)
            {
                tmpMatrix.setElement(i, j, paramMatrix.getElement(j, i));
            }
        }
        return tmpMatrix;
    }

    public static Matrix add(Matrix first, Matrix second) throws NotEqualLengthsOfMatrixException {
        if(first.getVerticalLength() != second.getVerticalLength() ||
                first.getHorizontalLength() != second.getHorizontalLength())
        {
            throw  new NotEqualLengthsOfMatrixException();
        }
        else {
            Matrix tmpMatrix = new Matrix(first.getVerticalLength(), second.getHorizontalLength());
            for (int i = 0; i < tmpMatrix.getHorizontalLength(); i++) {
                for(int j = 0; j < tmpMatrix.getVerticalLength(); j++){
                    tmpMatrix.setElement(i, j, first.getElement(i, j) + second.getElement(i, j));
                }
            }
            return tmpMatrix;
        }
    }

    public static Matrix subtract (Matrix first, Matrix second) throws NotEqualLengthsOfMatrixException {
        if(first.getVerticalLength() != second.getVerticalLength() ||
                first.getHorizontalLength() != second.getHorizontalLength())
            throw  new NotEqualLengthsOfMatrixException();
        else {
            Matrix tmpMatrix = new Matrix(first.getVerticalLength(), second.getHorizontalLength());
            for (int i = 0; i < tmpMatrix.getHorizontalLength(); i++) {
                for(int j = 0; j < tmpMatrix.getVerticalLength(); j++){
                    tmpMatrix.setElement(i, j, first.getElement(i, j) - second.getElement(i, j));
                }
            }
            return tmpMatrix;
        }
    }
    public static Matrix multiply (Matrix first, Matrix second) throws NotEqualLengthsOfMatrixException {
        if(first.getHorizontalLength() != second.getVerticalLength())
            throw  new NotEqualLengthsOfMatrixException();
        else {
            Matrix tmpMatrix;
            int n = first.getVerticalLength();
            int m = second.getHorizontalLength();
            int o = second.getVerticalLength();
            int[][] tmpArr = new int[n][m];
            for(int i = 0; i < n; i++){
                for(int j = 0; j < m; j++){
                    for (int k = 0; k < o; k++) {
                        tmpArr[i][j] += first.getElement(i, k) * second.getElement(k, j);
                    }
                }
            }
            tmpMatrix = new Matrix(tmpArr);
            return tmpMatrix;
        }
    }
}


class NotEqualLengthsOfMatrixException extends Exception {}


class MatrixMain {

    public static void main(String[] args) throws java.lang.Exception
    {
        //int[][] A = {{-1, 1, -1}, {1, -1, 1}, {-1, 1, -1}};
        //int[][] B = {{1, -1, 1}, {-1, 1, -1}, {1, -1, 1}};

        int[][] A =   {{33,34,12},
                       {33,19,10},
                       {12,14,17},
                       {84,24,51},
                       {43,71,21}};

        int[][] B =  {{10,11,34,55},
                      {33,45,17,81},
                      {45,63,12,16}};




        Matrix x = new Matrix(A);
        Matrix y = new Matrix(B);
        x.displayMatrix();
        y.displayMatrix();

        Matrix mM = Matrix.multiply(x, y);

        mM.displayMatrix();
        
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

class Matrix {

int n, m;

int[][] mainMatrix;

public Matrix(int n, int m)

{

this.n = n;

this.m = m;

this.mainMatrix = new int[this.n][this.m];

}

public Matrix(int [][] paramMatrix)

{

this.n = paramMatrix.length;

this.m = paramMatrix[0].length;

this.mainMatrix = paramMatrix;

}

public int getElement(int n, int m)

{

return this.mainMatrix[n][m];

}

public void setElement(int n, int m, int value)

{

this.mainMatrix[n][m] = value;

}

public int getVerticalLength()

{

return this.mainMatrix.length;

}

public int getHorizontalLength()

{

return this.mainMatrix[0].length;

}

public void fillRandomValues()

{

Random rand = new Random();

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

{

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

{

this.mainMatrix[i][j] = rand.nextInt(100);

}

public void displayMatrix()

{

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

{

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

{

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

}

System.out.println();

}

public static int[][] transpone(int[][] paramMatrix)

{

int[][] tmpMatrix = new int[paramMatrix[0].length][paramMatrix.length];

for(int i = 0; i < paramMatrix[0].length; i++)

{

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

{

tmpMatrix[i][j] = paramMatrix[j][i];

}

return tmpMatrix;

}

public static Matrix transpone(Matrix paramMatrix)

{

Matrix tmpMatrix = new Matrix(paramMatrix.m, paramMatrix.n);

for(int i = 0; i < paramMatrix.m; i++)

{

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

{

tmpMatrix.setElement(i, j, paramMatrix.getElement(j, i));

}

return tmpMatrix;

}

public static Matrix add(Matrix first, Matrix second) throws NotEqualLengthsOfMatrixException {

if(first.getVerticalLength() != second.getVerticalLength() ||

first.getHorizontalLength() != second.getHorizontalLength())

{

throw new NotEqualLengthsOfMatrixException();

}

else {

Matrix tmpMatrix = new Matrix(first.getVerticalLength(), second.getHorizontalLength());

for (int i = 0; i < tmpMatrix.getHorizontalLength(); i++) {

for(int j = 0; j < tmpMatrix.getVerticalLength(); j++){

tmpMatrix.setElement(i, j, first.getElement(i, j) + second.getElement(i, j));

}

return tmpMatrix;

}

public static Matrix subtract (Matrix first, Matrix second) throws NotEqualLengthsOfMatrixException {

if(first.getVerticalLength() != second.getVerticalLength() ||

first.getHorizontalLength() != second.getHorizontalLength())

throw new NotEqualLengthsOfMatrixException();

else {

Matrix tmpMatrix = new Matrix(first.getVerticalLength(), second.getHorizontalLength());

for (int i = 0; i < tmpMatrix.getHorizontalLength(); i++) {

for(int j = 0; j < tmpMatrix.getVerticalLength(); j++){

tmpMatrix.setElement(i, j, first.getElement(i, j) - second.getElement(i, j));

}

return tmpMatrix;

}

public static Matrix multiply (Matrix first, Matrix second) throws NotEqualLengthsOfMatrixException {

if(first.getHorizontalLength() != second.getVerticalLength())

throw new NotEqualLengthsOfMatrixException();

else {

Matrix tmpMatrix;

int n = first.getVerticalLength();

int m = second.getHorizontalLength();

int o = second.getVerticalLength();

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

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

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

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

tmpArr[i][j] += first.getElement(i, k) * second.getElement(k, j);

}

tmpMatrix = new Matrix(tmpArr);

return tmpMatrix;

}

class NotEqualLengthsOfMatrixException extends Exception {}

class MatrixMain {

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

{

//int[][] A = {{-1, 1, -1}, {1, -1, 1}, {-1, 1, -1}};

//int[][] B = {{1, -1, 1}, {-1, 1, -1}, {1, -1, 1}};

int[][] A = {{33,34,12},

{33,19,10},

{12,14,17},

{84,24,51},

{43,71,21}};

int[][] B = {{10,11,34,55},

{33,45,17,81},

{45,63,12,16}};

Matrix x = new Matrix(A);

Matrix y = new Matrix(B);

x.displayMatrix();

y.displayMatrix();

Matrix mM = Matrix.multiply(x, y);

mM.displayMatrix();

}

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

Пояснения

Класс Matrix имеет следующие поля: n, m — размеры основной матрицы, и сама матрица mainMatrix , представлена в виде двумерного массива целочисленного типа. Также данный класс имеет два конструктора: первый из которых принимает как параметры размеры создаваемой матрицы public Matrix(int n, int m) , второй же принимает как параметр двумерный массив(матрицу) public Matrix(int [][] paramMatrix) .

Данный класс имеет следующие методы:

public int getElement(int n, int m) — метод для получения элемента матрицы по индексам;
public void setElement(int n, int m, int value) — метод задания элемента по индексам;
public int getVerticalLength() — метод получения количества строк в матрице;
public int getHorizontalLength() — метод получения количества столбцов в матрице;
public void fillRandomValues() — метод заполнения матрицы рандомными значениями;
public void displayMatrix() — метод вывода матрицы;
public static int[][] transpone(int[][] paramMatrix) — метод транспонирования матрицы, с двумерным массивом как параметр;
public static Matrix transpone(Matrix paramMatrix) — метод транспонирования матрицы, с объектом класса Matrix , как параметр;
public static Matrix add(Matrix first, Matrix second) — метод нахождения суммы двух матриц;
public static Matrix subtract (Matrix first, Matrix second) — метод вычитания одной матрицы из другой;
public static Matrix multiply (Matrix first, Matrix second) — метод произведения двух матриц.

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

А136в

01/07/2017 by Шостак Дмитрий

Задача

Даны натуральное число [latex]n[/latex], действительные числа [latex]a_1,\ldots, a_n[/latex]. Вычислить: [latex]|a_1|+\ldots+|a_n|[/latex].

Тесты

№	n	[latex]a_1,\ldots, a_n[/latex]	Результат
1	3	3.31 -2.11 8.21	13.63
2	6	-12.1 -2.56 9 5 -2 4	34.66
3	2	-3.65 -3.11	6.76

Решение

class StreamLab
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner input = new Scanner(System.in);
		int n;
		double a, sum = 0;
		n = input.nextInt();
		for(int i = 1; i <= n; i++)
		{
			a = input.nextDouble();
			sum += Math.abs(a);
		}
		System.out.println(sum);
	}
}

class StreamLab

{

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

{

Scanner input = new Scanner(System.in);

int n;

double a, sum = 0;

n = input.nextInt();

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

{

a = input.nextDouble();

sum += Math.abs(a);

}

System.out.println(sum);

}

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

Пояснения

С начала вводим количество элементов [latex]n[/latex], после чего, в цикле по i от 1 до [latex]n[/latex] вводим элементы и суммируем их значение по модулю в переменную sum , по выходу из цикла выводим сумму в консоль.

ML2

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

Задача

Даны действительные числа [latex]x[/latex] и [latex]y[/latex]. Получить [latex]\frac{|x|-|y|}{|x|+|y|}[/latex].

Тесты

№	Входные данные	Выходные данные
1	3 7	-0.4
2	-5 -2	0.4285
3	-6 4	0.2
4	2 -3	-0.2

Решение

class FirstLab
{
	public static void main (String[] args)
	{
		double x, y, solution;
		Scanner input = new Scanner(System.in);
		
		x = input.nextDouble();
		y = input.nextDouble();
		
		solution = (Math.abs(x) - Math.abs(y)) / (Math.abs(x) + Math.abs(y));
		
		System.out.println(solution);
	}
}

class FirstLab

{

public static void main (String[] args)

{

double x, y, solution;

Scanner input = new Scanner(System.in);

x = input.nextDouble();

y = input.nextDouble();

solution = (Math.abs(x) - Math.abs(y)) / (Math.abs(x) + Math.abs(y));

System.out.println(solution);

}

Проверить работу кода можно в облаке по ссылке — http://ideone.com/h12CNL

Пояснения

Используя тип double объявляем переменные x, y и solution. После, инициализируем переменные x и y значениями из потока ввода. Далее, находим решение нашего выражения при использовании метода abs() библиотеки Math. Решение присваиваем ранее объявленной переменной solution, после чего выводим его в консоль.

Ю4.15

06/07/2016 by Дарья Пиндус

Заданы массивы $A(n)$ и $B(m)$ . Получить массив $C(m+n)$ , расположив в начале его элементы массива $A$ , а затем элементы массива $B$ .

Тесты:

n	m	A[n]	B[m]	Результат:
3	4	0 1 2	5 7 8 4	A={0 1 2} B={5 7 8 4} C={0 1 2 5 7 8 4}
2	9	9 3.6	7.4 3.6 4.6666 7.99702 1 1 1 1 1	A={9 3.6} B={7.4 3.6 4.6666 7.99702 1 1 1 1 1} C={9 3.6 7.4 3.6 4.6666 7.99702 1 1 1 1 1}

Код

import java.util.*;
import java.lang.*;
import java.io.*;
 
class U415 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n, m;
        n = scanner.nextInt();
        m = scanner.nextInt();
        double[] A = new double[n];
        double[] B = new double[m];
        double[] C = new double[n + m];
        for (int i = 0; i < n; i++) {
            A[i] = scanner.nextDouble();
        }
        for (int i = 0; i < m; i++) {
            B[i] = scanner.nextDouble();
        }
        for (int i = 0; i < n + m; i++) {
            if (i < n) {
                C [i] = A[i];
            } else {
                C [i] = B[i - n];
            }
        }
        System.out.println(Arrays.toString(C));
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class U415 {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

int n, m;

n = scanner.nextInt();

m = scanner.nextInt();

double[] A = new double[n];

double[] B = new double[m];

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

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

A[i] = scanner.nextDouble();

}

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

B[i] = scanner.nextDouble();

}

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

if (i < n) {

C [i] = A[i];

} else {

C [i] = B[i - n];

}

System.out.println(Arrays.toString(C));

}

Решение
Задаем размерности массивов. Вводим их. Затем заполняем массив $C$ элементами сначала из массива $A$ ( $A$ элементов), а затем (с $A$ -ого элемента ) — элементами из массива $A$ . Выводим массив $C$ .

Код на ideone.com

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

Tag Archives: задачи

e-olymp 975. Флойд

Задача

Тесты

Решение

Пояснения

Класс для хранения матриц

Задача

Тесты

Решение

Пояснения

А136в

Задача

Тесты

Решение

Пояснения

ML2

Задача

Тесты

Решение

Пояснения

Ю4.15