e-olymp 458. Черно-белая графика

Задача

Одна из базовых задач компьютерной графики – обработка черно-белых изображений. Изображения можно представить в виде прямоугольников шириной $w$ и высотой $h,$ разбитых на $w × h$ единичных квадратов, каждый из которых имеет либо белый, либо черный цвет. Такие единичные квадраты называются пикселами. В памяти компьютера сами изображения хранятся в виде прямоугольных таблиц, содержащих нули и единицы.

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

Напишите программу, которая вычислит результат попиксельного применения заданной логической операции к двум черно-белым изображениям одинакового размера.

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

Первая строка содержит два целых числа $w$ и $h$ $(1 \leq w, h \leq 100).$ Последующие $h$ строк описывают первое изображение и каждая из этих строк содержит $w$ символов, каждый из которых равен нулю или единице. Далее следует описание второго изображения в аналогичном формате. Последняя строка содержит описание логической операции в виде четырех чисел, каждое из которых – ноль или единица. Первое из них есть результат применения логической операции в случае, если оба аргумента нули, второе – результат в случае, если первый аргумент ноль, второй единица, третье – результат в случае если первый аргумент единица, второй ноль, а четвертый – в случае, если оба аргумента единицы.

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

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

Тесты

Входные данные Выходные данные
 1 5 3
01000
11110
01000
10110
00010
10110
0110
11110
11100
11110
2 2 3
010
111
000
101
1010
11
10
10
3 4 4
1111
0101
0000
1110
0011
0101
0111
1111
0011
1111
0101
0000
1110
4 3 6
100011
000111
000000
111011
001100
010101
1000
000
100
110
000
101
010

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

( использован одномерный массив)

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

(использован двумерный массив)

Решение

Объявляем два булевых динамических массива под две пиксельные таблицы и один статический для таблицы истинности, вводим входные данные. Затем поочерёдно сравниваем соответствующие элементы массивов с помощью функции my_operation, которая принимает две переменные a и b булевского типа и булев массив res с таблицей истинности, и возвращает соответствующее значение из таблицы для комбинации значений a и b. Результат сравнения выводим.

Ссылки

e-olymp 54. Мурзик

Задача

Весна… Прекрасное время! Все, казалось бы оживает и двигается, расцветает, начинается новый проход цикла жизни. И общеизвестный Мурзик не является исключением! Но если он чрезвычайно активен днем – то точно так же крепко спит ночью. Причем несчастный хищник видит преимущественно кошмары…

Одной ночью ему приснилось, что он судья на математических соревнованиях крыс (да, в наш век цифровых технологий даже крысы не остаются за гранью научно-технического прогресса). Соревнования проводятся среди [latex]N[/latex] команд по [latex]K[/latex] крыс в каждой. Соревнования проводятся в [latex]К[/latex] раундов, в каждом из которых представитель команды называет число. Побеждает та команда, у которой произведение всех чисел наибольшее. Почему крысы не называют каждый раз максимально возможное число? На то они и крысы, что в отличии от Мурзика, обделены интеллектом. Но и Мурзик понимает, что сам подсчитать результат не сможет из-за недостачи математических способностей и поэтому просит вашей помощи.

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

Первая строка содержит два целых числа [latex]N[/latex] и [latex]K[/latex] [latex](0 < N ≤ 20, 0 < K ≤ 100000)[/latex]. Следующие [latex]K[/latex] строк содержат по N чисел, которые называют представители команд. Причем крысы, как представители образованного вида, знают только 32-битовые знаковые числа.

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

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

Тесты

# Входные данные Выходные данные
1 3 3
20 10 30
15 20 20
30 30 20
3
2 3 3
20 -10 -30
15 25 20
30 -30 20
1
1 3 3
0 -10 -30
15 25 20
30 -30 20
2

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

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

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

Ссылки

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

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_с$ и $m_c$. В последующих $n_с$ строках вывести через пробел по $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
Умножение матриц на Wikipedia

e-olymp 2669. Поворот

Поворот

Дан массив [latex]n[/latex] × [latex]m[/latex]. Требуется повернуть его по часовой стрелке на [latex]90[/latex] градусов.

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

В первой строке даны натуральные числа [latex]n[/latex] и [latex]m[/latex] [latex](1 ≤ n, m ≤ 50)[/latex]. На следующих [latex]n[/latex] строках записано по [latex]m[/latex] неотрицательных чисел, не превышающих [latex]109[/latex] — сам массив.

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

Выведите перевернутый массив в формате входных данных.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 2 2

1 2

3 4

2 2

3 1

4 2

2 3 3

1 2 3

4 5 6

7 8 9

3 3

4 7 1

8 5 2

9 6 3

3 3 4

4 5 7 8

3 6 8 7

2 2 4 5

4 3

2 3 4

2 6 5

4 8 7

5 7 8

4 1 2

5 4

2 1

5

4

5 1 1

2

1 1

2

 

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

Алгоритм решения данной задачи состоит в том, чтоб при выводе матрицы, начать выводить ее элементы не по строкам, а по столбцам, снизу вверх, начиная с первого столбца (левого нижнего угла матрицы).

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 2261. Защита королевства

Защита королевства

Теодор реализует новую стратегию игры «Оборона Царства». На каждом уровне игрок защищает королевство, которое представлено прямоугольной сеткой ячеек. В некоторых клетках игрок строит арбалетные башни. Башня защищает все клетки в той же строке и том же столбце. Никакие две башни не находятся на одной строке или столбце.

Штрафом положения является количество клеток в крупнейшем незащищенном прямоугольнике. Например, положение, показанное на рисунке имеет штраф [latex]12[/latex].
Помогите Теодору написать программу, вычисляющую штраф в заданной позиции.

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

Первая строка содержит три целых числа: [latex]w[/latex] — ширина сетки, [latex]h[/latex] — высота сетки и [latex]n[/latex] — количество арбалетных башен [latex](1 ≤ w, h ≤ 40000; 0 ≤ n ≤ min(w, h))[/latex].

Каждая из следующих n строк содержит два целых числа [latex]x_i[/latex] и [latex] y_i[/latex] — координаты клетки с башней [latex](1 ≤ x_i ≤ w; 1 ≤ y_i ≤ h)[/latex].

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

Вывести одно число — количество клеток в наибольшем прямоугольнике, не защищенном башнями.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 10 10 3

1 1

2 2

3 3

49
2 15 15 4

4 4

5 5

7 8

13 15

30
3 30 30 5

13 14

16 27

29 30

5 5

10 15

132
4 100 100 2

1 1

100 100

9604
5 3 3 3

1 1

2 2

3 3

0

 

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

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

Алгоритм решения задачи состоит в том, чтобы найти максимальное количество незащищенных клеток между соседними башнями по координатам абсцисс и ординат (которые будет на [latex]1[/latex] меньше чем сама разность координат) и перемножить полученные числа тем самым найдя площадь образованного ими прямоугольника.

Для решения данной задачи нужно создать два массива в [latex]x[/latex] и [latex]y[/latex] (в первом будут находится [latex]x_i[/latex] координаты, а во втором [latex]y_i[/latex]) размера на [latex]2[/latex] больше чем количество заданных башен, так как нужно учитывать рамки поля, для чего достаточно добавить две башни c координатами [latex]\left(0;0\right)[/latex] и [latex]\left(x_{max}+1; y_{max}+1\right).[/latex]  Далее нужно отсортировать эти массивы и найти максимальную разность между соседними элементами ([latex]a[/latex] — максимальная разность между [latex]x_i[/latex] элементами, [latex]b[/latex] — максимальная разность между [latex]y_i[/latex]). Далее, по формуле [latex]\left(a-1\right)\cdot\left(b-1\right)[/latex] находим площадь самого большого незащищенного прямоугольника, которая равна количеству клеток в нем, что и является ответом задачи.

 

e-olymp 7447. Обрезка строки

Задача с сайта e-olymp.com.

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

Имеется строка [latex]s[/latex]. Разрешается взять два любых одинаковых соседних символа и удалить их из строки. Эту операцию можно производить пока имеется возможность. Сначала Вы можете выбрать любое количество символов в строке и удалить их. Определить наименьшее количество символов, которое Вы можете удалить сначала так, чтобы затем выполняя разрешенную операцию, получить пустую строку.

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

Содержит строку [latex]s[/latex] ([latex]1 ≤[/latex] длина[latex]\left( s \right) [/latex] [latex]≤ 100)[/latex].

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

Вывести наименьшее количество символов, которое следует удалить сначала.

Тесты

Входные данные Выходные данные
1 abbcddka 2
2 ABBA 0
3 abcde 5
4 abbac 1

Код на C++

Код на Java

Описание

Идея решения состоит в том, чтобы разбить строку на меньшие по длине подстроки и найти ответ на задачу для каждой из них. Для хранения строки используется переменная s, а ответы на подзадачи содержатся в двумерном массиве целых чисел answers. В answers[i][j] находится ответ для подстроки с i-ого по j-й символ включительно. В функции main сначала вводится строка s. Далее ширина и глубина массива answers устанавливаются равными длине s. После этого он заполняется начальными значениями. Значение [latex]-1[/latex] означает, что ответ для этой ячейки ещё не был найден. Однако очевидно, что если строка состоит ровно из одного символа, согласно условию задачи, его придётся удалить, значит, главную диагональ можно сразу заполнить единицами. Затем происходит вызов рекурсивной функции calculate, принимающей индексы левой и правой границ целевой подстроки. Первый раз она вызывается для всей строки от первого до последнего символа. Работает эта функция следующим образом: если индекс левой границы отрезка больше индекса правой, что, в случае данной задачи, не имеет смысла, она возвращает ноль. Иначе она возвращает ответ на задачу для данной подстроки, а если этого не делалось ранее, то предварительно находит его. Происходит это так: сначала значение ответа устанавливается равным длине подстроки, поскольку в худшем случае необходимо будет удалить её всю целиком. Если символы на концах подстроки одинаковые, они, как сказано в условии, будут удалены в дальнейшем, потому нужно рассматривать минимум из текущего значения ответа и ответа для подстроки без крайних символов. Однако может оказаться, что выгоднее удалить символы из каких-то двух меньших подстрок, потому далее в цикле рассматриваются все возможные комбинации двух подстрок, из которых можно составить конкатенацией текущую. В итоге получаем ответ на задачу для данной подстроки.

Код на ideone.com. (C++)
Код на ideone.com. (Java)
Засчитанное решение на e-olymp.

e-olymp 1521. Оптимальное умножение матриц

Задача

Имея два двумерных массива [latex]A[/latex] и [latex]B[/latex], мы можем вычислить [latex]C = AB[/latex] используя стандартные правила умножения матриц. Число колонок в массиве [latex]A[/latex] должно совпадать с числом строк массива [latex]B[/latex]. Обозначим через [latex]rows(A)[/latex] и [latex]columns(A)[/latex] соответственно количество строк и колонок в массиве [latex]A[/latex]. Количество умножений, необходимых для вычисления матрицы [latex]C[/latex] (ее количество строк совпадает с [latex]A[/latex], а количество столбцов с [latex]B[/latex]) равно [latex]rows(A) columns(B) columns(A)[/latex]. По заданной последовательности перемножаемых матриц следует найти оптимальный порядок их умножения. Оптимальным называется такой порядок умножения матриц, при котором количество элементарных умножений минимально.

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

Каждый тест состоит из количества [latex]n (n ≤ 10)[/latex] перемножаемых матриц, за которым следуют [latex]n[/latex] пар целых чисел, описывающих размеры матриц (количество строк и столбцов). Размеры матриц задаются в порядке их перемножения. Последний тест содержит [latex]n = 0[/latex] и не обрабатывается.

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

Пусть матрицы пронумерованы [latex]A_{1}[/latex], [latex]A_{2}[/latex],…, [latex]A_{n}[/latex]. Для каждого теста в отдельной строке следует вывести его номер и скобочное выражение, содержащее оптимальный порядок умножения матриц. Тесты нумеруются начиная с [latex]1[/latex]. Вывод должен строго соответствовать формату, приведенному в примере. Если существует несколько оптимальных порядков перемножения матриц, выведите любой из них.

Тесты

 №  Входные данные  Выходные данные
 1 3
1 5
5 20
20 1
3
5 10
10 20
20 35
6
30 35
35 15
15 5
5 10
10 20
20 25
0
Case 1: (A1 x (A2 x A3))
Case 2: ((A1 x A2) x A3)
Case 3: ((A1 x (A2 x A3)) x ((A4 x A5) x A6))
 2  10
653 273
273 692
692 851
851 691
691 532
532 770
770 690
690 582
582 519
519 633
0
Case 1: (A1 x ((((((((A2 x A3) x A4) x A5) x A6) x A7) x A8) x A9) x A10))
 3  2
11 12
12 33
7
1 5
5 28
28 19
19 2
2 10
10 1
1 12
4
10 29
29 133
133 8
8 15
0
Case 1: (A1 x A2)
Case 2: (((((A1 x A2) x A3) x A4) x (A5 x A6)) x A7)
Case 3: ((A1 x (A2 x A3)) x A4)

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

Засчитанное решение на e-olymp.com

Решение

Пусть [latex]A[/latex]- любая не последняя матрица заданной последовательности, [latex]B[/latex] — матрица, что следует за [latex]A[/latex] в данной последовательности перемножаемых матриц. Заведём двумерный массив [latex]dp[/latex] размером [latex] {(n+1)}\times {(n+1)}[/latex]. По главной диагонали массива запишем размеры матриц, причём [latex]rows(B)[/latex] не будем записывать, так как [latex]rows(B)=columns(A)[/latex]. В dp[k][j] [latex]\left( j<k \right) [/latex] будем хранить минимальное количество операций необходимое для получения матрицы [latex]C_{kj}[/latex] такой, что [latex]columns(C_{kj})[/latex] равно элементу dp[k][k], а [latex]rows(C_{kj})[/latex] соответственно dp[j][j]. Для получения матрицы [latex]C_{kj}[/latex] нужно умножить матрицу [latex]C_{k(j+t)}[/latex] на [latex]C_{(j+t)j}[/latex] [latex](\left( k-j \right) >t>0)[/latex], для этого нам понадобиться [latex]rows(C_{k(j+t)}) columns(C_{(j+t)j}) columns(C_{k(j+t)}) [/latex], что равно dp[k][k]*dp[j][j]*dp[j+t][j+t], операций непосредственно на перемножение этих матриц, а также dp[k][j+t] и dp[j+t][j] операций для получения матриц [latex]C_{k(j+t)}[/latex] и [latex]C_{(j+t)j}[/latex] соответственно.
Тогда dp[k][j]=dp[k][j+t]+dp[j+t][j]+dp[k][k]*dp[j][j]*dp[j+t][j+t]. При помощи цикла подберём [latex] t [/latex], при котором значение dp[k][j] выходит минимальным. Для получения матриц, которые даны изначально, не требуется ни одной операции, поэтому диагональ массива прилегающую к главной диагонали оставим заполненной нулями. Далее, при помощи вложенных циклов на каждом шаге внешнего цикла будем заполнять диагональ массива, что расположена ниже предыдущей. Параллельно будем запоминать номер последнего умножения, который будет равен [latex]j+t[/latex], в элемент массива, который расположен симметрично  dp[k][j] относительно главной диагонали (то есть в dp[j][k]). Таким образом от умножения двух исходных матриц поэтапно перейдём к оптимальному произведению [latex]n[/latex] матриц. Затем, рекурсивно восстановим оптимальный порядок умножения матриц. Для вывода ответа в соответствующем формате также воспользуемся рекурсией.

Ссылки

А406

Задача

С помощью [latex]x_{ij}, i=1,2; j=1,\ldots,n.[/latex] — действительной матрицы на плоскости задано n точек так, что [latex]x_{1j}, x_{2j}[/latex] — координаты [latex]j[/latex] — точки. Точки попарно соединены отрезками. Найти длину наибольшего отрезка.

Тест

n Матрица [latex]x_{ij}, i=1,2.[/latex] Длина наибольшего отрезка  Комментарий
3  

2 8 4

9 1 5

10 Пройдено
4  

6 14 2 1

9 3 8 0

13.3417 Пройдено
5  

1 8 4 3 7

2 9 5 0 11

11.7047 Пройдено

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

Ход решения:

  1. Вводим матрицу построчно (не очень удобно).
  2. Находим длину наибольшего отрезка.
    С помощью вложенных циклов мы находим длины всех отрезков по формуле
    [latex] AB=\sqrt{(x_{2}-x_{1})^{2}+(y_{2}-y_{1})^{2}}, A(x_{1},y_{1}), B(x_{2},y_{2}). [/latex]
  3. По алгоритму нахождения максимума находим длину наибольшего отрезка.
  4. Выводим матрицу.
  5. Выводим длину наибольшего отрезка.
    Ссылка на код

А694а

Задача: Получить квадратную матрицу порядка [latex]n[/latex]

[latex]\begin{pmatrix}1 &0 &\cdots & 0 \\ 0 & 1 &\cdots &0 \\ \cdots &\cdots &\cdots \cdots & \cdots \\ 0 & 0 & \cdots & 1\end{pmatrix}[/latex]

Тесты:

n Матрица
3 1 0 0

0 1 0

0 0 1

4 1 0 0 0

0 1 0 0

0 0 1 0

0 0 0 1

6 1 0 0 0 0 0

0 1 0 0 0 0

0 0 1 0 0 0

0 0 0 1 0 0

0 0 0 0 1 0

0 0 0 0 0 1

Ход работы:
1. С помощью цикла заполняем главную диагональ единицами.

2. Приравниваем элементы не равные единице к нулю.

3. Вывод массива.

Ссылка на код

А1035

Задача. Указать маршрут коня. Начинающегося на одном заданном поле шахматной доски и оканчивающемся на другом. Никакое поле не должно встречаться в маршруте дважды.

Пример

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

b1

a1
b3
d2
b1
a1
h8
a1
c2
e3
g2
h4
g6
h8

 

Решение

Читаем входные данные. Преобразуем их в координаты начального и финального поля на шахматной доске. Массив chessboard  сначала заполняем -1 (не пройденные поля), затем значение в поле с начальными координатами присваиваем 0. Затем будем отмечать все доступные ходы коня до тех пор пока не изменится значение в финальном поле. Затем, если у нас не совпали начальное и финальное поле будем восстанавливать путь коня. Создаем массив в котором и будет путь коня. Первое значение которое мы заносим в массив будет наше финальное поле. Затем с этого поля будем рассматривать все возможные ходы которые пройдут по уже помеченным клеткам. Если в финальное поле можно было попасть несколькими путями одинаковой длины то нам не имеет значение каким из них возвращаться в начальное поле. Затем выводим массив пути в обратном порядке.

Код на ideone.

А702а

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

2
1 2
3 4
0.666667 1.66667
Пройдено
2
5 6
7 8
2.66667 3.66667
Пройдено

При рассмотрении ряда квадратов чисел [latex](1, 4 , 9, \dots)[/latex], заметно, что числа следующей степени увеличиваются на четные числа, при этом модификатор предыдущего элемента на [latex]2[/latex] меньше чем следующего.
Все что нам остается сделать, это добавить генерацию вектора [latex]b[/latex], через модифицирующий элемент (преимущества которого состоят в частности, в том, что мы намного ускоряем вычисления квадратов, используя уже имеющиеся нас данные), в первый цикл (цикл ввода матрицы [latex]a[/latex]), а во втором цикле уже организовать вывод и вычисление собственно результирующего вектора.

Код программы: http://ideone.com/bl2iJE.

А407

Задача:
Даны натуральные числа n и m, действительное число r, действительная матрица размера nxm. Получить значение [latex]{b}_{1}{r}^{n-1}+{b}_{2}{r}^{n-2}+\dots+{b}_{n}[/latex], где [latex]{b}_{k}[/latex] — первый по порядку положительный элемент в k-й строке матрицы [latex](k=1,\dots,n)[/latex]; если в k-строке нет положительных элементов, то [latex]{b}_{k}=0.5[/latex].

Тесты:

nxm r Матрица Результат Комментарий
2х2 2.5 [latex]\begin{pmatrix} -1 & 1 \\ 1 & 0 \end{pmatrix}[/latex]  3.5 Пройдено
 3×4  3.14 [latex]\begin{pmatrix}5.7 & 6.7 & -7.7 & 0.9\\-3.0 & 2.3 & -5.0 & -2.4\\6.7 & 3.5 & 0.0 & 4.4\end{pmatrix}[/latex]  70.1 Пройдено
 2×4  2.71 [latex]\begin{pmatrix}-9.0 &-8.8 &-7.3 & 7.5\\-6.3 &-9.7 & 6.8 &-0.5\end{pmatrix}[/latex]  27.1 Пройдено

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

Код программы на Java:

Идея решения:
Считать n, m как целочисленные переменные. После этого считать r как переменную типа double. Следующим считать массив nxm созданный благодаря генератору матриц из случайных чисел заданного размера. Завести переменную [latex]sum = 0[/latex] для хранения результата. Проверять построчно каждый столбик на наличие положительного числа и прибавить первое положительное число в строке, умноженное на [latex]{r}^{n-i-1}[/latex], к результаты. В случает отсутствия положительного элемента в строке,  брать 0.5. В конце вывести результат.

Ю4.32

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

Матрица Суммы
1 2 3
4 5 6
7 8 9
7 12 15 8 3
-1 2 -3 4
10 5 11 6
-7 8 -9 2
12 5 13 6
12 -2 31 1 15 3 4
0 0
0 0
0 0 0

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

Сначала вводим размер квадратной матрицы —  [latex]n[/latex]. Создаем одномерный массив [latex]b[/latex] в который будет результат. В нем будет [latex]2n-1[/latex] элементов, которые мы заполняем нулями.После чего в цикле будем накапливать суммы [latex]b[i-j+n-1]+=a[i][j].[/latex].

При  [latex]i=j[/latex], мы записываем сумму диагоналей в  [latex]b[n-1][/latex], который находиться в середине нашего массива  [latex]b[/latex], как нам и нужно.
Если  [latex]i>j[/latex], мы записываем суммы в элементы после середины нашего массива [latex]b[/latex].
Если  [latex]i<j[/latex], мы записываем суммы в элементы до середины нашего массива [latex]b[/latex].
Константу, которая нам нужна, будем искать по формуле [latex] max(j) — min(i)[/latex], которая равна [latex]n-1[/latex].

Код программы можно посмотреть тут

А401

Дана действительная квадратная матрица порядка [latex]n[/latex], натуральные числа [latex]i, j \left(1\leq i\leq n, 1\leq j\leq n \right)[/latex]. Из матрицы удалить [latex]i[/latex]-строку и [latex]j[/latex]-столбец.

[latex]n[/latex] Матрица. [latex]i[/latex] [latex]j[/latex] Полученная матрица. Комментарий.
3 1 2 3

4 5 6

7 8 9

2 1 2 3

8 9

Тест пройден.
4 0,5 1 6 0

3 8 12 0,3

10 4,6 8 9

0 3,5 6,4 10

4 3 0,5 1 0

3 8 0,3

10 4,6 9

Тест пройден.
2 -40 87

9 -3

1 1 -3 Тест пройден.

Код программы (C++):

Java:

 

Сначала пользователю предлагается ввести порядок матрицы, затем элементы этой матрицы. После чего, по условию задачи, пользователь должен задать [latex]i[/latex]-строку и [latex]j[/latex]-столбец, которые программа должна изъять из матрицы.

Протестировать программу можно здесь (C++) и здесь (Java).

Ю4.27

Задача Ю4.27. Сессия. Результаты сессии, состоящей из трёх экзаменов, для группы из [latex]n[/latex] студентов представлены матрицей [latex]K \left(n,3 \right)[/latex]. Оценка ставится по четырёхбалльной системе; неявка обозначена единицей. Подсчитать количество неявок, неудовлетворительных, удовлетворительных, хороших и отличных оценок по каждому экзамену.

[latex]n[/latex] Оценки. Результат. Комментарий.
3 5 3 1

4 3 5

5 2 3

1: неявка (1), уд (1), отл (1).

2: уд (1), хор (1), отл (1).

3: неуд (1), уд (1), отл (1).

Тест пройден.
6 5 4 2 1 1 3

3 2 1 4 4 2

5 5 3 4 2 1

1: неявка (2), неуд (1), уд (1), хор (1), отл (1).

2: неявка (1), неуд (2), уд (1), хор (2).

3: неявка (1), неуд (1), уд (1), хор (1), отл (2).

Тест пройден.
2 2 4

1 5

3 3

1: неуд (1), хор (1).

2: неявка (1), отл (1).

3: уд (2).

Тест пройден.

Код программы (C++):

Java:

 

Изначально пользователю предлагается ввести количество студентов [latex]n[/latex]. Затем создаётся массив  [latex]K \left(n,3\right)[/latex], в котором будут храниться оценки студентов, а так же двумерный массив [latex]o \left(5,3 \right)[/latex], который, собственно говоря, и будет хранить статистику по оценкам. Внешний цикл перебирает экзамены (по [latex]j[/latex]), а внутренний — студентов (по [latex]i[/latex]). Затем пользователю предлагается ввести оценки студентов (сначала вводятся все оценки за первый экзамен, затем за второй, а потом уж за третий). В этом цикле находится «счётчик», который подсчитывает количество определённых оценок (или неявок) в зависимости от массива [latex]K \left(n,3\right)[/latex] на данном этапе цикла. Затем на экран выводятся элементы массива (в дальнейшем все элементы сохранятся, то есть с оценками студентов можно будет работать и дальше).

Код программы можно посмотреть тут (C++) и тут (Java).

Skynet: the Virus

Skynet


SKYNET FINALE — LEVEL 1


Вирус

Los Angeles 2029 — Resistance HQ — Review of facts:

В минувшую субботу, сотни отважных бойцов рисковали своей жизнью, чтобы уничтожить Skynet. СТОП

Используя зараженных мото-терминаторов, им удалось привить смертельный вирус к Skynet. СТОП

Проблема: Skynet борется. СТОП

Джон, ещё раз,  нам нужна ваша помощь. СТОП


Задача:

У нас в распоряжении целый граф узлов. Некоторые из них названы шлюзами. Шлюзы надо защищать от злобного Skynet агента, который способен передвигаться по связям между узлами. Способ защиты очень прост: каждый ход можно навсегда заблокировать одну связь, тем самым, через некоторое количество ходов, полностью закрыть шлюз от нежелательных гостей.

Первичная инициализация:

Первая строка: 3 целых числа N L E

  • N — Количество узлов, включая шлюзы
  • L — Количество связей
  • E — Количество шлюзов

Следующие L строк: по два числа на строку (N1, N2), означающие, что между узлами с индексами N1 и N2 присутствует связь.
Следующие E строк: по одному числу на строку, означающие индексы шлюзов.

Инициализация за каждый игровой тик:

Одно число — индекс связи, на которой находится Skynet агент.

Вывод за каждый игровой тик:

Одна строка в которой присутствует два числа C1 и C2. C1 и C2 — это индексы двух узлов, между которыми мы хотим заблокировать переход. Если между ними нет связи, возникает ошибка. В конце строки обязательно должен стоить символ перехода на новую строку.

Программа:

Идея решения: Всё предельно просто: Если агент находится вблизи одного из шлюзов, закрываем переход между агентом и этим шлюзом. Иначе закрываем переход между шлюзом и ближайшим узлом.

Переходы между узлами занесены в двумерный массив N1, далее этот массив был своеобразно отсортирован (для удобства). В игровом цикле объявляем булевую переменную AgentIsNear — агент вблизи шлюза.

Первый цикл: Проверяем каждую клетку вокруг каждого шлюза на присутствие там агента. И если он таки там есть, блокируем переход, меняем первую переменную (отвечающую за шлюз) в массиве переходов (N1) на -1 (значение, которое никогда не встретится), изменяем AgentIsNear на true и прерываем цикл.

Второй цикл: так как агент гуляет где-то далеко, то мы блокируем любой свободный проход любого шлюза.

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

Программа проходит все тесты на MEDIUM и, что удивительно, половину тестов на HARD! Взято с CodinGame