e-olimp 9536. Сумма матриц

20/09/2020 by Елизавета Савицкая

Задача

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

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

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

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

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

Тесты

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

Код

class Main{
	public static void main (String[] args) throws java.lang.Exception 	{
		java.util.Scanner i = new java.util.Scanner(System.in);
		int n = i.nextInt();
		int m = i.nextInt();
		int array1[][] = new int[n][m];
		int array2[][] = new int[n][m];
		int array_sum[][] = new int[n][m];
		for(int k = 0; k < n; k++){
        	for(int j = 0; j < m; j++){
        		array1[k][j] = i.nextInt();
    		}
		}
		for(int k = 0; k < n; k++){
        	for(int j = 0; j < m; j++){
        		array2[k][j] = i.nextInt();
    		}
		}
		for(int k = 0; k < n; k++){
        	for(int j = 0; j < m; j++){
        		array_sum[k][j] = array1[k][j] + array2[k][j];
        		System.out.print (array_sum[k][j] + " ");
    		}
    		System.out.println();
		}
	}
}

class Main{

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

java.util.Scanner i = new java.util.Scanner(System.in);

int n = i.nextInt();

int m = i.nextInt();

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

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

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

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

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

array1[k][j] = i.nextInt();

}

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

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

array2[k][j] = i.nextInt();

}

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

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

array_sum[k][j] = array1[k][j] + array2[k][j];

System.out.print (array_sum[k][j] + " ");

}

System.out.println();

}

Решение

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

Ссылки

Условие задачи на E-Olymp
Код задачи на Ideone

e-olymp 1661. Рюкзак Алладина

09/09/2020 by Валентин Цушко

Условие

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

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

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

Будем считать, что в пещере имеются предметы $n$ различных типов, количество предметов каждого типа не ограничено. Максимальный вес, который может выдержать рюкзак, равен $w$. Каждый предмет типа $i$ имеет вес $w_{i}$ и стоимость $v_{i}$ $(i = 1, 2, \ldots, n)$.

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

В первой строке содержится два натуральных числа $w$ и $n$ $(1 \leqslant w \leqslant 250, 1 \leqslant n \leqslant 35)$ — максимальный вес предметов в рюкзаке и количество типов предметов. Следующие $n$ строк содержат по два числа $w_{i}$ и $v_{i}$ $(1 \leqslant w_{i} \leqslant 250, 1 \leqslant v_{i} \leqslant 250)$ — вес предмета типа $i$ и его стоимость.

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

Выведите максимальную стоимость груза, вес которого не превышает $w$.

Тесты

№	Входные данные	Выходные данные
1	10 2 5 10 6 19	20
2	250 35 187 100 28 109 245 142 123 83 237 78 36 172 15 248 90 24 181 137 40 233 8 99 231 128 79 132 43 217 156 104 45 191 130 113 105 225 206 5 26 120 26 119 64 138 23 147 19 202 79 54 149 185 158 79 209 88 110 133 235 209 188 230 15 220 107 164 235 137 60 167	4067
3	35 4 20 4 1 2 10 8 7 6	70

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

public class Main
{
	public static void main(String[] args) {
	    
	    java.util.Scanner in = new java.util.Scanner(System.in);
	    
		int w, n;
        int NegNum = -1;
        w = in.nextInt();
        n = in.nextInt();
        int WeiCos[][], s[];
        WeiCos = new int [n][2];
        s = new int [w + 1];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < 2; j++){
                WeiCos[i][j] = in.nextInt();
            }
        }
        s[0] = 0;
        for(int j = 1; j <= w; j++){
            s[j] = NegNum;
        }
            for(int i = 0; i < n; i++){
            for(int j = WeiCos[i][0]; j <= w; j++){
                if(s[j - WeiCos[i][0]] != NegNum && s[j] < s[j - WeiCos[i][0]] + WeiCos[i][1]){
                    s[j] = s[j - WeiCos[i][0]] + WeiCos[i][1];
                }
            }
        }  
        int maxS = 0;
        for(int i = 1; i <= w; i++){
            maxS = Math.max(maxS, s[i]);
        }
        System.out.print(maxS);
	}
}

public class Main

{

public static void main(String[] args) {

java.util.Scanner in = new java.util.Scanner(System.in);

int w, n;

int NegNum = -1;

w = in.nextInt();

n = in.nextInt();

int WeiCos[][], s[];

WeiCos = new int [n][2];

s = new int [w + 1];

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

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

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

}

s[0] = 0;

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

s[j] = NegNum;

}

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

for(int j = WeiCos[i][0]; j <= w; j++){

if(s[j - WeiCos[i][0]] != NegNum && s[j] < s[j - WeiCos[i][0]] + WeiCos[i][1]){

s[j] = s[j - WeiCos[i][0]] + WeiCos[i][1];

}

int maxS = 0;

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

maxS = Math.max(maxS, s[i]);

}

System.out.print(maxS);

}

Решение

Допустим $w = 9$, $n = 2$, первый предмет $w_{1} = 3$, $n_{1} = 4$, а второй предмет $w_{2} = 2$, $n_{2} = 1$. После того как считаем условие в два одномерных или один двумерный массив (как вам удобнее). Создадим одномерный массив в котором его размер будет равен $w$ и первый элемент будет равен 0, а остальные будут равны минус бесконечности или как в нашем случае (в коде) -1, как показано на (рис. 1). И дальше как показано на (рис. 2) начиная с элемента с номером веса предмета мы прибавляем его стоимость к стоимости предыдущей как показано в коде s[j] = s[j - WeiCos[i][0]] + WeiCos[i][1];, если прошлый не минус бесконечность. И так же со вторым элементом, когда они пересекаются с первым мы их сравниваем и вписываем в массив, больший. И в самом конце проходим заново массив и выбираем самый больший элемент, где бы он ни был как показано на (рис. 3). И таким образом на последних позициях которые равняются весу, будут записаны самые дорогие комбинации, благодаря записи самых дорогих элементов в ячейки.

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

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

09/09/2020 by Валентин Цушко

Условие

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

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

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

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

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

Тесты

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

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

class Main{
    public static void main (String[] args) throws java.lang.Exception {
    java.util.Scanner in = new java.util.Scanner(System.in);

    int n, m = 1;
    n = in.nextInt();
    int a[][];

    a = new int [n][n];

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

    for(int i = 0; i < (n / 2); i++){
        for(int j = i; j < (n - i); j++){ // (n - i) - чтоб с каждым разом сторона становилась меньше
            a[i][j] = m;
            m++;
        }
        for(int j = 1; j = i; j--){ // (n - 2) - i - отнимаем 1 чтоб не выходило за рамки массива и еще одну 1
            a[(n - i) - 1][(j)] = m; // потому-что предыдущий эл. уже заполнен.
            m++;
        }
        for(int j = ((n - i) - 2); j > i; j--){
            a[j][i] = m;
            m++;
        }
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n - 1; j++){
            System.out.print(a[i][j] + " ");
        }
        System.out.println(a[i][n - 1]);
    }
}
}

class Main{

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

java.util.Scanner in = new java.util.Scanner(System.in);

int n, m = 1;

n = in.nextInt();

int a[][];

a = new int [n][n];

if(n % 2 != 0){

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

}

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

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

a[i][j] = m;

m++;

}

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

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

m++;

}

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

a[j][i] = m;

m++;

}

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

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

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

}

System.out.println(a[i][n - 1]);

}

Решение

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

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

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

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

А701б

24/02/2019 by Глеб Брошко

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

Даны квадратная матрица [latex]A[/latex] порядка [latex]n[/latex] и вектор [latex]b[/latex] c [latex]n[/latex] элементами. Получить вектор \[A^{2} \cdot b\]

Алгоритм решения

Считываем матрицу. Возводим ее в квадрат ( перемножение матрицы осуществляется при помощи циклов). Считываем вектор. Умножаем матрицу на вектор. Выводим ответ.

Фактически, умножение матриц пишется по определению. Сумма произведений элементов строки на элементы столбцов.

Тесты

[latex]n[/latex]	[latex]A[/latex]	[latex]b[/latex]	Результат
3	1 1 1 1 1 1 1 1 1	5 5 5	45 45 45
5	1 0 0 0 0 0 2 0 0 0 0 0 3 0 0 0 0 0 4 0 0 0 0 0 5	8 1 8 1 8	8 4 72 16 200
2	1 0 0 1	2 2	2 2

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

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int n;
		double matr1[][];
		double matr2[][];
		double vet1[];
		double vet2[];
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		matr1 = new double[n][n];  //Матрица А 
		matr2 = new double[n][n]; // Матрица А^2
		vet1 = new double[n];  //Вектор данный по условию (вектор b)
		vet2 = new double[n];  //Конечный вектор
 
		for(int i = 0;i < n;i++){
			for(int j = 0; j < n; j++) // Инициализация матрицы А
				matr1[i][j] = sc.nextInt();
		}
 
		for(int i = 0; i < n;i++){
			for(int j = 0;j < n;j++){  //Возведение матрицы А в квадрат
				matr2[i][j] = 0;
				for(int p = 0;p < n;p++)
					matr2[i][j] += (matr1[i][p]*matr1[p][j]);
			}
		}
 
		for(int i = 0; i < n; i++)                //Инициализация вектора
			v
			et1[i] = sc.nextInt();
 
		for(int i = 0;i < n;i++){
			vet2[i] = 0;
			for(int j=0; j<n; j++){
				vet2[i] += matr2[i][j]*vet1[j]; //Умножение матрицы на вектор
			}
		}
 
		for(int i = 0; i < n; i++)
			System.out.println(vet2[i]);       //Вывод вектора
 
		sc.close();
 
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

int n;

double matr1[][];

double matr2[][];

double vet1[];

double vet2[];

Scanner sc = new Scanner(System.in);

n = sc.nextInt();

matr1 = new double[n][n]; //Матрица А

matr2 = new double[n][n]; // Матрица А^2

vet1 = new double[n]; //Вектор данный по условию (вектор b)

vet2 = new double[n]; //Конечный вектор

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

for(int j = 0; j < n; j++) // Инициализация матрицы А

matr1[i][j] = sc.nextInt();

}

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

for(int j = 0;j < n;j++){ //Возведение матрицы А в квадрат

matr2[i][j] = 0;

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

matr2[i][j] += (matr1[i][p]*matr1[p][j]);

}

for(int i = 0; i < n; i++) //Инициализация вектора

et1[i] = sc.nextInt();

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

vet2[i] = 0;

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

vet2[i] += matr2[i][j]*vet1[j]; //Умножение матрицы на вектор

}

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

System.out.println(vet2[i]); //Вывод вектора

sc.close();

}

Код на ideone.com.

Задача оригинал на языке С++(другого автора) на java.mazurok.com.

e-olymp 2671. Сапер

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

Задача

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

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

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

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

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

Тесты

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

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

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int m = scanner.nextInt();
		int bomb = scanner.nextInt();
		int count = 0;
		char[][] A = new char[34][34];
		for (int i = 0; i < bomb; i++){
        int x = scanner.nextInt();
        int y = scanner.nextInt();
        A[x][y] = '*';
    	}
    	for (int i = 1; i < n + 1; i++){
        for (int j = 1; j < m + 1; j++){ 
            if (A[i][j] != '*'){
                if (A[i-1][j] == '*') count++;
                if (A[i-1][j-1] == '*') count++;
                if (A[i-1][j+1] == '*') count++;
                if (A[i+1][j+1] == '*') count++;
                if (A[i+1][j-1] == '*') count++;
                if (A[i+1][j] == '*') count++;
                if (A[i][j-1] == '*') count++;
                if (A[i][j+1] == '*') count++;
                System.out.print(count);
                count = 0;
            }
            else System.out.print(A[i][j]);
            if (j != m) System.out.print(" ");;
        }
        System.out.print("\n");
    	}
	}
}

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt();

int m = scanner.nextInt();

int bomb = scanner.nextInt();

int count = 0;

char[][] A = new char[34][34];

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

int x = scanner.nextInt();

int y = scanner.nextInt();

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

}

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

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

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

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

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

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

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

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

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

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

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

System.out.print(count);

count = 0;

}

else System.out.print(A[i][j]);

if (j != m) System.out.print(" ");;

}

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

}

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

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

Ссылки

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

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

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

27/12/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

Код решения

import java.io.InputStream;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        new Resolver(System.in, System.out).solve();
    }

    public static class Resolver {

        private Scanner scanner;
        private PrintWriter writer;

        public Resolver(InputStream is, OutputStream os) {
            this.scanner = new Scanner(is);
            this.writer = new PrintWriter(os);
        }

        public void solve() {
            int rowCount = scanner.nextInt();
            int columnCount = scanner.nextInt();
            int[][] chocolate = new int[rowCount][columnCount];
            for (int i = 0; i < rowCount; i++) {
                for (int j = 0; j < columnCount; j++) chocolate[i][j] = scanner.nextInt();
            }
            check(chocolate, rowCount, columnCount);
            writer.flush(); writer.close();
        }

        private void check(int[][] chocolate, int rowCount, int columnCount) {
            if (BreakRow(chocolate, rowCount, columnCount) || BreakColumn(chocolate, rowCount, columnCount)) writer.println("Yes");
            else writer.println("No");
        }
        private boolean BreakRow(int[][] chocolate, int rowCount, int columnCount) {
            for (int i = 0; i < rowCount - 1; i++) {
                boolean okRow = true;
                for (int j = 0; j < columnCount; j++) {
                    if (chocolate[i][j] == chocolate[i + 1][j]) { okRow = false; break; }
                }
                if (okRow) return true;
            }
            return false;
        }
        private boolean BreakColumn(int[][] chocolate, int rowCount, int columnCount) {
            for (int i = 0; i < columnCount - 1; i++) {
                boolean okColumn = true;
                for (int j = 0; j < rowCount; j++) {
                    if (chocolate[j][i] == chocolate[j][i + 1]) { okColumn = false; break; }
                }
                if (okColumn) return true;
            }
            return false;
        }
    }
}

import java.io.InputStream;

import java.io.OutputStream;

import java.io.PrintWriter;

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

new Resolver(System.in, System.out).solve();

}

public static class Resolver {

private Scanner scanner;

private PrintWriter writer;

public Resolver(InputStream is, OutputStream os) {

this.scanner = new Scanner(is);

this.writer = new PrintWriter(os);

}

public void solve() {

int rowCount = scanner.nextInt();

int columnCount = scanner.nextInt();

int[][] chocolate = new int[rowCount][columnCount];

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

for (int j = 0; j < columnCount; j++) chocolate[i][j] = scanner.nextInt();

}

check(chocolate, rowCount, columnCount);

writer.flush(); writer.close();

}

private void check(int[][] chocolate, int rowCount, int columnCount) {

if (BreakRow(chocolate, rowCount, columnCount) || BreakColumn(chocolate, rowCount, columnCount)) writer.println("Yes");

else writer.println("No");

}

private boolean BreakRow(int[][] chocolate, int rowCount, int columnCount) {

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

boolean okRow = true;

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

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

}

if (okRow) return true;

}

return false;

}

private boolean BreakColumn(int[][] chocolate, int rowCount, int columnCount) {

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

boolean okColumn = true;

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

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

}

if (okColumn) return true;

}

return false;

}

Решение

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

Ссылки

Ссылка на E-olymp
Ссылка на решение

e-olymp 936. Формулы Крамера

27/12/2018 by Иван Василевский

Условие задачи
Решить систему двух линейных уравнений с двумя неизвестными по формулам Крамера. Система уравнений, приведенная во входных данных, имеет вид:
$\begin{cases} 5x_1+8x_2=11 \\ -3x_1+6x_2=15 \end{cases}$
Входные данные
Первая строка содержит коэффициенты первого уравнения, а вторая строка содержит коэффициенты второго. Все входные числа разделены одним пробелом и не превышают по модулю $100$.
Выходные данные
Первый корень системы уравнений вывести в первой строке, а второй корень во второй строке с точностью до $0.001$.
Тесты

Входные данные	Выходные данные
5 8 1 -3 6 15	-1.000 2.000
5 5 5 2 3 5	-2.000 3.000
1 2 3 3 3 3	-1.000 2.000
25 15 16 11 12 13	-0.022 1.104

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        double matrix[][] = new double[3][2];
        for (int i = 0; i < 2; ++i){
            String[] params1 = bufferedReader.readLine().split(" ");
            for (int j = 0; j < 3; ++j){
                matrix[j][i] = Float.parseFloat(params1[j]);
            }
        }
        double d = matrix[0][0] * matrix[1][1] - matrix[0][1] * matrix[1][0];
        double d1 = matrix[2][0] * matrix[1][1] - matrix[2][1] * matrix[1][0];
        double d2 = matrix[0][0] * matrix[2][1] - matrix[0][1] * matrix[2][0];
        System.out.printf("%.3f\n%.3f\n", d1 / d, d2 / d);
	}
}

import java.io.BufferedReader;

import java.io.InputStreamReader;

class Main

{

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

{

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

double matrix[][] = new double[3][2];

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

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

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

matrix[j][i] = Float.parseFloat(params1[j]);

}

double d = matrix[0][0] * matrix[1][1] - matrix[0][1] * matrix[1][0];

double d1 = matrix[2][0] * matrix[1][1] - matrix[2][1] * matrix[1][0];

double d2 = matrix[0][0] * matrix[2][1] - matrix[0][1] * matrix[2][0];

System.out.printf("%.3f\n%.3f\n", d1 / d, d2 / d);

}

Решение задачи
Создаем матрицу размером $3$ на $2$, так как у нас $3$ переменных в $2$ уравнениях. Создаем циклы для заполнения нашей матрицы. Дальше по формуле Камера перемножаем переменные. Выводим на экран ответы с точностью до $0.001$.
Ссылки
Задача на сайте e-olymp
Код решения в Ideone

e-olymp 2812. Уголок

26/12/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

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		String[] params1 = bufferedReader.readLine().split(" ");
		int x, y;
        x = Integer.parseInt(params1[0]);
        y = Integer.parseInt(params1[1]);
        boolean mas[][] = new boolean[x][y];
        for (int i = 0; i < x; ++i){
            String[] params2 = bufferedReader.readLine().split(" ");
            for (int j = 0; j < y; ++j){
                char buff;
                buff = params2[0].charAt(j);
                if (buff == '.') mas[i][j] = true; 
                else mas[i][j] = false;
            }
            System.out.print("\n");
        }
        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; 
                }
            }
        }
        System.out.print(sum);
	}
}

import java.io.BufferedReader;

import java.io.InputStreamReader;

class Main

{

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

{

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

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

int x, y;

x = Integer.parseInt(params1[0]);

y = Integer.parseInt(params1[1]);

boolean mas[][] = new boolean[x][y];

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

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

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

char buff;

buff = params2[0].charAt(j);

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

else mas[i][j] = false;

}

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

}

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;

}

System.out.print(sum);

}

Решение

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

Ссылки

e-olymp
Ideone

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

26/12/2018 by Андрей Лисовой

Задача

Позиция короля на шахматной доске

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

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

Возможные ходы короля

Вводные данные

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

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

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

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

Тесты

Входные данные	Выходные данные
$5\;1\;2\;4\;7\;4$	$4$
$5\;1\;2\;4\;6\;4$	$Ok$ $2$
$8\;3\;3\;7\;7\;5\;5\;3\;3$	$3$
$12\;2\;3\;4\;1\;3\;2\;5\;6\;8\;2\;1\;7$	$10$
$9\;2\;2\;3\;3\;4\;4\;7\;7\;7$	$Ok$ 2

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

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int[][] x = new int[2001][2001];
		int n = in.nextInt();
		int move;
		int xPos=1001, yPos=1001;
		for(int i = 0; i < n; i++) {
			move = in.nextInt();
			if(x[xPos][yPos] == 1) { 
            	System.out.print(i);
            	return;
        	}
        	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--;
	        }
		}
		System.out.print("Ok" + "\n" + (Math.abs(xPos-1001)+Math.abs(yPos-1001)));
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

Scanner in = new Scanner(System.in);

int[][] x = new int[2001][2001];

int n = in.nextInt();

int move;

int xPos=1001, yPos=1001;

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

move = in.nextInt();

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

System.out.print(i);

return;

}

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

}

System.out.print("Ok" + "\n" + (Math.abs(xPos-1001)+Math.abs(yPos-1001)));

}

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

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

Ссылки

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

e-olymp 5080. Количество висячих вершин 1

25/12/2018 by Карина Миловская

Задача

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

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

В первой строке находится число $n$ $\left ( 1 \leq n \leq 1000 \right ).$ В следующих $n$ строках находится матрица смежности.

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

Выведите количество висячих вершин в графе.

Тесты

Входные данные	Выходные данные
$2 \\ 0 \ 1 \\ 1 \ 0$	$2$
$3 \\ 0 \ 1 \ 1 \\ 1 \ 0 \ 1 \\ 1 \ 1 \ 0$	$0$
$4 \\ 1 \ 0 \ 0 \ 0 \\ 0 \ 1 \ 0 \ 0 \\ 0 \ 0 \ 1 \ 0 \\ 0 \ 0 \ 0 \ 1$	$4$
$3 \\ 0 \ 1 \ 1 \\ 1 \ 0 \ 1 \\ 1 \ 0 \ 0$	$1$

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

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int [][] gr = new int [1001][1001]; 
		Scanner in = new Scanner(System.in);
		int n = in.nextInt(); 
		int ans = 0; 
		for (int i=0; i<n; i++) {
			for (int j=0; j<n; j++) {
				gr[i][j] =  in.nextInt(); 
			}
		}
		for (int i=0; i<n; i++) {
			int cnt = 0; 
			for (int j=0; j<n; j++) {
				if (gr[i][j] == 1) cnt++;
			}
			if (cnt==1) ans++;
		}
		System.out.println(ans);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

int [][] gr = new int [1001][1001];

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int ans = 0;

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

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

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

}

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

int cnt = 0;

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

if (gr[i][j] == 1) cnt++;

}

if (cnt==1) ans++;

}

System.out.println(ans);

}

Решение

Введем обозначения: $gr$ – имя массива(матрицы смежности), $n$ – количество вершин, $cnt$ – счётчик.
Просматривая матрицу смежности, подсчитываем количество единиц, т.е количество инцидентных вершин данной вершине. Инцидентные вершины — вершины, которые соединены ребром. Степенью вершины называется количество рёбер, инцидентных этой вершине. Висячей вершиной называют вершину, степень которой равна 1. Соответственно, если в каком-либо ряду в матрице только одна единица, то вершина имеет степень 1 и является висячей.
Сперва предположим, что что граф не имеет висячих вершин, далее введём матрицу смежности, подсчитаем степень вершины и проверим, является ли вершина висячей. В ответе выводим количество висячих вершин в графе.

Ссылки

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

Код решения задачи ideone

Задача

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

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

Тесты

Код

Решение

Ссылки

Условие

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

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

Тесты

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

Решение

Условие

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

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

Тесты

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

Решение

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

Алгоритм решения

Тесты

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

Задача

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

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

Тесты

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

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

Ссылки

Задача

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

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

Код решения

Решение

Ссылки

5 8 1 -3 6 15

-1.000 2.000

5 5 5 2 3 5

-2.000 3.000

1 2 3 3 3 3

-1.000 2.000

25 15 16 11 12 13

-0.022 1.104

Задача

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

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

Тесты

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

Решение

Ссылки

Задача

Вводные данные

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

Тесты

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

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

Ссылки

Задача

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

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

Тесты

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

Решение

Ссылки

5 8 1
-3 6 15

-1.000
2.000

5 5 5
2 3 5

-2.000
3.000

1 2 3
3 3 3

-1.000
2.000

25 15 16
11 12 13

-0.022
1.104