А701б

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

Даны квадратная матрица [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

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

Код на ideone.com.

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

e-olymp 2671. Сапер

Задача

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

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

Даны числа $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 *

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

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

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

Ссылки

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

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

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

Задача

Петя очень любит шоколад. И Маша очень любит шоколад. Недавно Петя купил шоколадку и теперь хочет поделиться ею с Машей. Шоколадка представляет собой прямоугольник $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

Код решения

Решение

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

Ссылки

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

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

Условие задачи
Решить систему двух линейных уравнений с двумя неизвестными по формулам Крамера. Система уравнений, приведенная во входных данных, имеет вид:
$\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

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

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

e-olymp 2812. Уголок

Задача

Дана прямоугольная доска [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

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

Решение

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

Ссылки

e-olymp
Ideone

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

Задача

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

Одинокий король долго бродил по бесконечной шахматной доске. Известна последовательность из $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

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

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

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

Ссылки

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

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

Задача

Дан простой неориентированный невзвешенный граф. Подсчитать количество висячих вершин в нем. Вершина называется висячей, если ее степень равна $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$

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

Решение

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

Ссылки

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

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

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

Задача

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

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

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

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

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

Тесты

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

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

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

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

Ссылки

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

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

e-olymp 1482. Умножение матриц

Задача

Пусть даны две прямоугольные матрицы $A$ и $B$ размерности $m \times n$ и $n \times q$ соответственно:
$$A = \begin{bmatrix} a_{11} & a_{12} & \ldots & a_{1n} \\ a_{21} & a_{22} & \ldots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \ldots & a_{mn} \end{bmatrix} \; , \; B = \begin{bmatrix} b_{11} & b_{12} & \ldots & b_{1q} \\ b_{21} & b_{22} & \ldots & b_{2q} \\ \vdots & \vdots & \ddots & \vdots \\ b_{n1} & b_{n2} & \ldots & b_{nq} \end{bmatrix} .$$
Тогда матрица $C$ размерностью $m \times q$ называется их произведением:
$$C = \begin{bmatrix} c_{11} & c_{12} & \ldots & c_{1q} \\ c_{21} & c_{22} & \ldots & c_{2q} \\ \vdots & \vdots & \ddots & \vdots \\ c_{m1} & c_{m2} & \ldots & c_{mq} \end{bmatrix} ,$$
где:
$$c_{i,j} = \sum_{r=1}^{n} a_{i,r}b_{r,j} \; \left(i = 1, 2, \ldots m; j = 1, 2, \ldots q\right).$$
Операция умножения двух матриц выполнима только в том случае, если число столбцов в первом сомножителе равно числу строк во втором; в этом случае говорят, что форма матриц согласована.

Задано две матрицы $A$ и $B$. Найти их произведение.

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

В первой строке задано $2$ натуральных числа $n_a$ и $m_a$ – размерность матрицы $A$. В последующих $n_a$ строках задано по $m_a$ чисел – элементы $a_{ij}$ матрицы $A$. В $\left(n_a + 2\right)$-й строке задано $2$ натуральных числа $n_b$ и $m_b$ – размерность матрицы $B$. В последующих $n_b$ строках задано по $m_b$ чисел – элементы $b_{ij}$ матрицы $B$. Размерность матриц не превышает $100 \times 100$, все элементы матриц целые числа, не превышающие по модулю $100$.

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

В первой строке вывести размерность итоговой матрицы $C$: $n_c$ и $m_c$. В последующих $n_c$ строках вывести через пробел по $m_c$ чисел – соответствующие элементы $c_{ij}$ матрицы $C$. Если умножать матрицы нельзя — в первой и единственной строке вывести число $-1$.

Тесты

Входные данные Выходные данные
2 3
1 3 4
5 -2 3
3 3
1 3 2
2 1 3
0 -1 1
2 3
7 2 15
1 10 7
3 3
1 5 3
2 6 1
7 -1 -3
3 2
3 6
-1 1
3 1
3 2
7 14
3 19
13 38
4 4
4 8 -18 16
3 7 14 -42
2 1 1 7
4 9 5 -2
4 4
1 0 0 0
0 1 0 0
0 0 1 0
4 4
4 8 -18 16
3 7 14 -42
2 1 1 7
4 9 5 -2
3 3
5 7 -1
8 9 3
0 -6 17
2 3
7 -15 1
8 8 2
-1
2 3
57 -49 31
89 11 -37
3 1
19
-19
0
2 1
2014
1482

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

Решение

Для начала, считываем данные матрицы $A$ из входного потока и записываем их в двумерный динамический массив. Далее, получив данные о размерности второй матрицы, мы можем определить, выполнима ли операция умножения, и если нет, то прервать выполнение программы. Если операция умножения данных матриц выполнима, то считываем и записываем данные второй матрицы, после чего, по приведённой выше формуле вычисляем произведение матриц $C = A \times B.$ Наконец, выводим полученную матрицу $C$.

Ссылки

Условие задачи на e-olymp
Решение на ideone
Решение на e-olymp
Умножение матриц на Wikipedia

e-olymp 2666. Половина

Задача

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

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

Дано натуральное число [latex]n[/latex] [latex](n \leqslant 20).[/latex]

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

Выведите массив, заполненный по указанному правилу.

Тесты

# Входные данные Выходные данные
1 2 20
01
2 3 220
201
011
3 4 2220
2201
2011
0111
4 5 22220
22201
22011
20111
01111
5 10 2222222220
2222222201
2222222011
2222220111
2222201111
2222011111
2220111111
2201111111
2011111111
0111111111

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

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

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

  • [latex]i + j = n — 1,[/latex] если ячейка [latex](i,j)[/latex] лежит на побочной диагонали;
  • [latex]i + j > n — 1,[/latex] если ячейка [latex](i,j)[/latex] лежит ниже побочной диагонали;
  • [latex]i + j < n — 1,[/latex] если ячейка [latex](i,j)[/latex] лежит выше побочной диагонали.

Далее заполняем массив в соответствии с введеными обозначениями и условием задачи, а затем выводим его на экран. Задача решена.

Ссылки

Ссылка на e-olymp
Ссылка на ideone