e-olymp 236. Триомино

14/09/2020 by Евгений Фищук

Триомино

Сколькими способами можно замостить прямоугольник $2 × n$ триоминошками? Триомино — это геометрическая фигура, составленная из трех квадратов, соединяющихся между собой вдоль полного ребра. Есть только две возможных триоминошки:

Например, замостить прямоугольник $2 × 3$ можно только тремя различными способами. Поскольку ответ может быть достаточно большим, искомое количество способов следует вычислять по модулю $10^6$.

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

Первая строка содержит количество тестов $t$ ($1 \leqslant t \leqslant 100$). Каждая из следующих $t$ строк содержит значение $n$ ($0 < n < 10^9$).

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

Для каждого теста в отдельной строке выведите количество способов, которыми можно замостить прямоугольник $2 × n$. Результат следует выводить по модулю $10^6$.

Тесты

№	Входные данные	Выходные данные
1	3 3 4 6	3 0 11
2	4 12 15 21 9	153 571 7953 41

Код

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


class Main
{
    static long MOD=1000000;
    static long[][] multiply(long[][] v1) {
        long[][] ans=new long[2][2];
        long x00 = v1[0][0];
        long x01 = v1[0][1];
        long x10 = v1[1][0];
        long x11 = v1[1][1];
        long res00, res01, res10, res11;
        res00 = ((x00 * x00) % MOD + (x10 * x01) % MOD) % MOD;
        res01 = ((x00 * x01) % MOD + (x01 * x11) % MOD) % MOD;
        res10 = ((x10 * x00) % MOD + (x10 * x11) % MOD) % MOD;
        res11 = ((x10 * x01) % MOD + (x11 * x11) % MOD) % MOD;
        ans[0][0]=(res00+MOD)%MOD;
        ans[0][1]=(res01-MOD)%MOD;
        ans[1][0]=(res10+MOD)%MOD;
        ans[1][1]=(res11-MOD)%MOD;
        return ans;
    }

    static long[][] pow_mod(long[][] v, int p) {
        if (p == 1) return v;
        //if ((p % 2) == 0)
        return multiply((pow_mod(v, p / 2)));
    }
    public static void main (String[] args)
    {
        Scanner in = new Scanner(System.in);

        int t=in.nextInt();
        for (int i = 0; i < t; i++)
        {
            int n=in.nextInt();
            if (n % 3!=0)
            {
                System.out.println(0);
            }
            else
            {
                n /= 3;
                int p = 2;
                long a1 = 1, a2 = 1;
                while (n > 0)
                {
                    if ((n & 1)==1)
                    {
                        long[][] a = { {4,-1},{1,0} };
                        a = pow_mod(a, p / 2);
                        long tmp1 = a1;
                        long tmp2 = a2;
                        a1 = (tmp1 * a[0][0]) % MOD + (tmp2 * ((a[0][1] + MOD) % MOD)) % MOD;
                        a2 = (tmp1 * a[1][0]) % MOD + (tmp2 * ((a[1][1] + MOD) % MOD)) % MOD;
                    }
                    p *= 2;
                    n >>= 1;
                }
                a1=a1%MOD;
                System.out.println(a1);
            }
        }
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

static long MOD=1000000;

static long[][] multiply(long[][] v1) {

long[][] ans=new long[2][2];

long x00 = v1[0][0];

long x01 = v1[0][1];

long x10 = v1[1][0];

long x11 = v1[1][1];

long res00, res01, res10, res11;

res00 = ((x00 * x00) % MOD + (x10 * x01) % MOD) % MOD;

res01 = ((x00 * x01) % MOD + (x01 * x11) % MOD) % MOD;

res10 = ((x10 * x00) % MOD + (x10 * x11) % MOD) % MOD;

res11 = ((x10 * x01) % MOD + (x11 * x11) % MOD) % MOD;

ans[0][0]=(res00+MOD)%MOD;

ans[0][1]=(res01-MOD)%MOD;

ans[1][0]=(res10+MOD)%MOD;

ans[1][1]=(res11-MOD)%MOD;

return ans;

}

static long[][] pow_mod(long[][] v, int p) {

if (p == 1) return v;

//if ((p % 2) == 0)

return multiply((pow_mod(v, p / 2)));

}

public static void main (String[] args)

{

Scanner in = new Scanner(System.in);

int t=in.nextInt();

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

{

int n=in.nextInt();

if (n % 3!=0)

{

System.out.println(0);

}

else

{

n /= 3;

int p = 2;

long a1 = 1, a2 = 1;

while (n > 0)

{

if ((n & 1)==1)

{

long[][] a = { {4,-1},{1,0} };

a = pow_mod(a, p / 2);

long tmp1 = a1;

long tmp2 = a2;

a1 = (tmp1 * a[0][0]) % MOD + (tmp2 * ((a[0][1] + MOD) % MOD)) % MOD;

a2 = (tmp1 * a[1][0]) % MOD + (tmp2 * ((a[1][1] + MOD) % MOD)) % MOD;

}

p *= 2;

n >>= 1;

}

a1=a1%MOD;

System.out.println(a1);

}

Решение

Если n нацело не делится на $3$, то выводится ноль,в ином случае данная задача решается через рекуррентную формулу $a_n=4*a_{n-1}-a_{n-2}$. Но из-за слишком больших чисел мы не можем использовать данную формулу просто так, поэтому мы воспользуемся быстрым вычислением членов рекуррентной последовательности через матрицы. Надо умножать матрицу

$\begin{pmatrix}
4&-1 \\\
1&0 \\\
\end{pmatrix}$ в степени $p$(где $p$ равна двойке в степени номера единицы в двоичной записи числа ${{n}\over{3}}$) на матрицу $\begin{pmatrix}
1\\\
1\\\
\end{pmatrix}$ каждый раз, когда встречается единица в двоичной записи числа ${{n}\over{3}}$. На выход подается первое число вектора $2 × 1$.

Ссылки

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

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

e-olymp 9036. Комбинация игральных костей

09/09/2020 by Алина Зозуля

Задача

Подсчитайте количество способов, которыми можно получить сумму $n$ бросая игральный кубик один или несколько раз. Каждый бросок дает результат между 1 и 6.

Например, если $n = 3$, то имеется 4 способа:
1 + 1 + 1
1 + 2
2 + 1
3

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

Одно целое число $n$ $(1 \leqslant n \leqslant 10^6)$.

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

Выведите количество способов по модулю $10^9+7$.

Тесты

№	Входные данные	Выходные данные
1	1	1
2	3	4
3	5	16
4	6	32
5	8	123

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

import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.Scanner;
public class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int n;
	    int ans = 0;
	    Scanner myObj = new Scanner(System.in);
	    n = myObj.nextInt(); //считываем сумму, для которой будем считать количество перестановок
	    int a[] = new int[n+1]; //создаем массив
	    Arrays.fill(a, 0);
	    if (n == 1) ans = 1;
	    if (n == 2) ans = 2;
	    if (n == 3) ans = 4;
	    if (n == 4) ans = 8;
	    if (n == 5) ans = 16;
	    if (n == 6) ans = 32;
	    // частные случаи
	    
	    if (n > 6)
	    {
	        a[1] = 1; 
	        a[2] = 2; 
	        a[3] = 4; 
	        a[4] = 8;
	        a[5] = 16; 
	        a[6] = 32; 
	        for (int i = 7; i < n + 1; i++)
	        {
	            a[i]=0;
	            for (int j = 1; j < 7; j++) // вычисление количества для i-ой суммы
	                a[i] = ( a[i] + a[i-j] ) % 1000000007;
	        }
	        ans = a[n];
	    }
	    
	    System.out.println(ans);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.util.Scanner;

public class Ideone

{

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

{

int n;

int ans = 0;

Scanner myObj = new Scanner(System.in);

n = myObj.nextInt(); //считываем сумму, для которой будем считать количество перестановок

int a[] = new int[n+1]; //создаем массив

Arrays.fill(a, 0);

if (n == 1) ans = 1;

if (n == 2) ans = 2;

if (n == 3) ans = 4;

if (n == 4) ans = 8;

if (n == 5) ans = 16;

if (n == 6) ans = 32;

// частные случаи

if (n > 6)

{

a[1] = 1;

a[2] = 2;

a[3] = 4;

a[4] = 8;

a[5] = 16;

a[6] = 32;

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

{

a[i]=0;

for (int j = 1; j < 7; j++) // вычисление количества для i-ой суммы

a[i] = ( a[i] + a[i-j] ) % 1000000007;

}

ans = a[n];

}

System.out.println(ans);

}

Решение

Создадим массив на $n+1$ элемент. В который мы сразу запишем количество перестановок для сумм 1,2..,6. Для остальных случаев, когда $n>7$ воспользуемся следующей идеей. Будем вычислять количество перестановок для сумм, начиная с 7 до тех пор, пока не дойдем до заданного нам $n$. Будем делать это по такой формуле $a_{i}=a_{i-1}+a_{i-2}+a_{i-3}+a_{i-4}+a_{i-5}+a_{i-6}$ . Для первых шести сумм вычисляем по этой же формуле, с учетом, что $0 < i-k \; (1 \leqslant k \leqslant 6)$ и добавляя еще 1 перестановку, так как мы можем получить сумму ( $i$ ), подбросив кубик 1 раз. Рассмотрим для $n=7$. Чтобы получить 7 достаточно подбросить кубик ещё один раз, так как мы знаем количество для $n$ от 1 до 6. Если выпадет 1, то остается $a_{6}$ возможных перестановок, если выпадет 2, то остается $a_{5}$ и так далее. Затем нам требуется просуммировать, так как кубик может выпасть 6 способами, как было сказано ранее. Соответственно для $n=8$ количество комбинаций увеличится на $a_{7}$ и уменьшится на $a_{1}$, так как кубик имеет только 6 граней.

Ссылки

Условие задачи на 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

Ю4.8

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

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

В массиве [latex]C(m)[/latex] заменить каждый третий элемент полусуммой двух предыдущих, а стоящий перед ним — полусуммой соседних с ним элементов.

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

1.Инициализируем переменную [latex]n[/latex], которая будет размером массива и сам массив [latex]a[/latex];
2.С помощью ввода задаем длину массива;
3.С помощью цикла и ввода заполняем массив;
3.Меняем каждый третий элемент начиная со второго;
4.Находим полусумму двух предыдущих элементов;
5.Берем число стоящее перед числом кратным трем;
6.Заменяем его на полусумму стоящих рядом элементов.

Тесты

Кол-во элементов	Элементы	Результат
3	5 9 1	5 3 7
6	8 7 6 9 4 0	8 7 7,5 9 4,5 6,5
9	2 5 7 3 6 9 4 6	2 4,5 3,5 3 6 4,5 4 5,5 5

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

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int n;						// Инициализируем переменную n;
		double a[];					// Инициализируем массив a;
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();				//Вводим размер массива;
		a = new double[n];						
		for(int i = 0; i < n ; ++i){
			a[i] = sc.nextInt();			//Вводим элементы массива;
		}
		if(n >= 3){
			for(int i = 2; i < n; i+=3){
				double tmp = a[i - 1];
				a[i - 1] = (a[i] + a[i - 2])/2;	//Находим полусумму двух предыдущих элементов;
				a[i] = (tmp + a[i - 2])/2;	//Заменяем число кратное трем на полусумму стоящих рядом элементов;
			}
			for(int i = 0; i < n ; ++i){
			System.out.println(a[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; // Инициализируем переменную n;

double a[]; // Инициализируем массив a;

Scanner sc = new Scanner(System.in);

n = sc.nextInt(); //Вводим размер массива;

a = new double[n];

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

a[i] = sc.nextInt(); //Вводим элементы массива;

}

if(n >= 3){

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

double tmp = a[i - 1];

a[i - 1] = (a[i] + a[i - 2])/2; //Находим полусумму двух предыдущих элементов;

a[i] = (tmp + a[i - 2])/2; //Заменяем число кратное трем на полусумму стоящих рядом элементов;

}

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

System.out.println(a[i]);

}

sc.close();

}

Код на ideone.com.

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

А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 5071. Проверка на неориенитрованность

03/01/2019 by Кирилл Бондаренко

Задача. Проверка на неориенитрованность

Условие задачи
По заданной квадратной матрице $n\times n$ из нулей и единиц определите, может ли данная матрица быть матрицей смежности простого неориентированного графа.

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

Входной файл содержит число $n(1\leq n\leq 100)$ — размер матрицы, и затем $n$ строк по $n$ чисел, каждое из которых равно $0$ или $1$ — саму матрицу.

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

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

Тесты

ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
3 0 1 1 1 0 1 1 1 0	YES
3 0 1 0 1 0 1 1 1 0	NO
3 0 1 0 1 1 1 0 1 0	NO
4 0 1 0 0 1 0 1 1 1 1 0 1 0 1 1 1	NO

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

import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.Scanner;
class Main {
	public static void main (String[] args) throws java.lang.Exception {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int k = n*n;
		int [] G = new int [k];
		for (int i = 0; i < G.length; i++) {
			G[i] = in.nextInt();
		}
		int j = 0, c = 0, s = 0;
		boolean f = true;
		for (int i = 0; i < k; i++) {
			if (G[i] != G[j]) {
				f=false;
				break;
			}
			if (c == n - 1) {
				c = 0;
				s++;
				j = s;
			} else {
				j = j + n;
				c++;
			}
		}
		for (int i = 0; i < k; i = i + n + 1) {
			if (G[i] != 0) {
				f = false;
				break;
			}
		}
		if (f) System.out.print("YES"); else System.out.print("NO");
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.util.Scanner;

class Main {

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

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int k = n*n;

int [] G = new int [k];

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

G[i] = in.nextInt();

}

int j = 0, c = 0, s = 0;

boolean f = true;

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

if (G[i] != G[j]) {

f=false;

break;

}

if (c == n - 1) {

c = 0;

s++;

j = s;

} else {

j = j + n;

c++;

}

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

if (G[i] != 0) {

f = false;

break;

}

if (f) System.out.print("YES"); else System.out.print("NO");

}

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

Чтобы введённая матрица была матрицей смежности простого неориентированного графа, она должна, во-первых, быть симметричной, то есть элементы на соответствующих позициях должны быть равны между собой: $a[i] = a[j]$. Во-вторых, необходимо, чтобы элементы главной диагонали матрицы равнялись нулю. Таким образом, нам нужно проверить, выполняются ли указанные условия.
Создаём переменную f типа bool. Изначально f=true. Если при проверке на симметричность и равенство нулю главной диагонали хоть одно значение элемента матрицы не удовлетворяет условию, флаг устанавливается в «ложь» и происходит выход из цикла проверки. Это означает соответственно, что введённая матрица не является матрицей смежности неориентированного графа, — на экран выводится «NO». Если же оба условия выполняются, приведённая матрица — матрица смежности. Выводим «YES».

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 2670.Координаты соседей

27/12/2018 by Илья Черноморец

Задача

Для клетки с координатами $\left(x, y\right)$ в таблице размером $M\times N$ выведите координаты ее соседей. Соседними называются клетки, имеющие общую сторону.

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

Даны натуральные числа $M, N, x, y \left(1 \leqslant x \leqslant M \leqslant 109, 1 \leqslant y \leqslant N \leqslant 109\right).$

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

В выходной файл выведите пары координат соседей этой клетки в произвольном порядке.

Тесты

Входные данные	Выходные данные
3 3 2 2	1 2 2 1 2 3 3 2
23 23 21 13	20 13 22 13 21 12 21 14
11 8 10 5	9 5 11 5 10 4 10 6

Код решения

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 n = in.nextInt();
                int m = in.nextInt();
                int x = in.nextInt();
                int y = in.nextInt();
		if (x > 1) System.out.print((x-1)+" "+y+"\n");
		if (x  1) System.out.print(x+" "+(y-1)+"\n");
		if (y < m) System.out.print(x+" "+(y+1)+"\n");
	}
}

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 n = in.nextInt();

int m = in.nextInt();

int x = in.nextInt();

int y = in.nextInt();

if (x > 1) System.out.print((x-1)+" "+y+"\n");

if (x 1) System.out.print(x+" "+(y-1)+"\n");

if (y < m) System.out.print(x+" "+(y+1)+"\n");

}

Решение

Для решения этой задачи стоит просмотреть все варианты координат соседних точек. То есть, нужно прибавить единицу к абсциссам и ординатам заданной точки. Но стоит учесть, что таблица у нас ограничена: $1 \leqslant x \leqslant M, 1 \leqslant y \leqslant N$

Ссылки

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

А410е

27/12/2018 by Антон Джашимов

Задача

Дана целочисленная матрица $ [a_{ij}], ij=1,\ldots,n.$ Получить $b_{1} \dots b_{n},$ где $b_{i}$ — это $\underset{1\leq j\leq n}{\max a_{ij}}\cdot \underset{1\leq j\leq n}{\min a_{ji}}$

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

Первая строка содержит число $n.$ Следующие строки содержат матрицу $n\times n.$

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

Вывести $b_i \; i=1\dots n.$

Тесты

Входные данные	Выходные данные
2 1 2 4 1	2 4
3 1 2 3 4 1 -6 1 -2 -1	3 -8 -6

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

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 n,maxa,mina;
		n=in.nextInt();
		int a[][];
		a = new int[n][];
    	for (int i = 0 ;i < n ; i++) {
			a[i] = new int [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]);
			System.out.print(" ");
    	}
	}
}

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 n,maxa,mina;

n=in.nextInt();

int a[][];

a = new int[n][];

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

a[i] = new int [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]);

System.out.print(" ");

}

Решение

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

Ссылки

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

Триомино

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

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

Тесты

№

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

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

Код

Решение

Ссылки

Задача

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

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

Тесты

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

Решение

Ссылки

Условие

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

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

Тесты

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

Решение

Условие

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

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

Тесты

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

Решение

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

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

Тесты

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

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

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

Тесты

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

Задача. Проверка на неориенитрованность

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

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

Тесты

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

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

Задача

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

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

Тесты

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

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

Ссылки

Задача

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

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

Тесты

Код решения

Решение

Ссылки

Задача

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

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

Тесты

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

Решение

Ссылки