По заданному нечетному натуральному числу [latex] n [/latex] вывести изображение размером [latex] n × n [/latex], образованное символами звездочка и пробел как показано в примере.
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
Входные данные
Одно нечетное натуральное число [latex] n (n>1)[/latex] .
Выходные данные
Вывести изображение [latex] n × n [/latex].
Тесты
Входные данные
Выходные данные
3
*
*
*
*
*
*
*
5
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
7
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
Код программы
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
usingnamespacestd;
intmain(){
intn;
cin>>n;
int**x=newint*[n];
for(inti=0;i<n;i++)x[i]=newint[n];
intm=(n-1)/2;
for(inti=0;i<n;i++){
for(intj=0;j<n;j++){
x[i][j]=1;
}
for(intj=i+1;j<n-i-1;j++){
x[i][j]=0;
}
}
for(inti=0;i<m;i++){
for(intj=0;j<n;j++){
if(x[i][j]==0){
x[n-i-1][j]=0;
}
}
}
for(inti=0;i<n;i++){
for(intj=0;j<n;j++){
if(x[i][j]!=0){
cout<<"*";
}elsecout<<" ";
}
cout<<endl;
}
return0;
}
Решение задачи
Считываем значение [latex]n[/latex]. Создаём двумерный массив [latex] n * n [/latex] все элементы которого равны единице. Далее в цикле заполняем пространство между [latex] * [/latex] нулями. Так как позиции [latex] (i,0)[/latex] и [latex] (i,n) [/latex] всегда [latex] * [/latex], ко второму счётчику [latex] j [/latex] прибавляем единицу . На середине [latex] m = ( n — 1 ) / 2 [/latex] цикл прекращает заполнение нулями, потому в следующем цикле верхняя часть отображается в нижнюю. После чего происходит вывод двумерного массива заменяя [latex] 0=« » [/latex] и [latex] 1=«*» [/latex].
По данному числу [latex]n[/latex] заполните квадратную матрицу размером [latex]n*n[/latex] целыми числами от [latex]1[/latex] до [latex]n^{2}[/latex] следующим образом:
в левом верхнем углу находится число [latex]1[/latex];
далее числа располaгаются «змейкой», т.е. по возрастанию слева направо в нечётных строках, и справа налево — в чётных;
Входные данные
Одно целое число [latex]n[/latex] [latex](1 \leqslant n \leqslant 100)[/latex].
Выходные данные
Вывести заполненную матрицу в виде [latex]n[/latex] строк по [latex]n[/latex] целых чисел в каждой.
Создаем переменные
flag_even для четных строк и
flag_odd для нечетных. Они будут содержать значение элемента матрицы на каждом шаге алгоритма в соответствующих строках.
Следует обратить внимание, что в условии указано, что числа идут слева направо в нечётных строках, и справа налево — в чётных, но в массивах нумерация идет с [latex]0[/latex] (четное число), поэтому в коде условие обратное.
В циклах выполняем операции и сразу же печатаем элементы матрицы.
Первая строка содержит размеры матрицы [latex]n[/latex] и [latex]m[/latex]. [latex]1 \leq m,n \leq 100 [/latex] Следующие [latex]n[/latex] строк содержат по [latex]m[/latex] целых чисел и описывают матрицу [latex]A[/latex].
Выходные данные
Выведите транспонированную матрицу [latex]A[/latex]: [latex]m[/latex] строк по [latex]n[/latex] целых чисел.
При получении первой матрицы мы получаем индекс каждого элемента — [latex]i[/latex], [latex]j[/latex] и количество строк и столбцов — [latex]n[/latex] и [latex]m[/latex]. Зная саму матрицу, количество строк и столбцов мы можем создать матрицу, где строк столько, сколько столбцов в первой матрице, и наоборот.
Сама же перестановка элементов происходит посредством смены индекса строки и столбца — элемент [latex]a[/latex] с индексом [latex]i[/latex] строки и [latex]j[/latex] столбца становится элементом [latex]b[/latex] с индексом [latex]j[/latex] строки и [latex]i[/latex] столбца.
Одна из базовых задач компьютерной графики – обработка черно-белых изображений. Изображения можно представить в виде прямоугольников шириной $w$ и высотой $h,$ разбитых на $w × h$ единичных квадратов, каждый из которых имеет либо белый, либо черный цвет. Такие единичные квадраты называются пикселами. В памяти компьютера сами изображения хранятся в виде прямоугольных таблиц, содержащих нули и единицы.
Во многих областях очень часто возникает задача комбинации изображений. Одним из простейших методов комбинации, который используется при работе с черно-белыми изображениями, является попиксельное применение некоторой логической операции. Это означает, что значение пиксела результата получается применением этой логической операции к соответствующим пикселам аргументов. Логическая операция от двух аргументов обычно задается таблицей истинности, которая содержит значения операции для всех возможных комбинаций аргументов. Например, для операции «ИЛИ» эта таблица выглядит так.
Напишите программу, которая вычислит результат попиксельного применения заданной логической операции к двум черно-белым изображениям одинакового размера.
Входные данные
Первая строка содержит два целых числа $w$ и $h$ $(1 \leq w, h \leq 100).$ Последующие $h$ строк описывают первое изображение и каждая из этих строк содержит $w$ символов, каждый из которых равен нулю или единице. Далее следует описание второго изображения в аналогичном формате. Последняя строка содержит описание логической операции в виде четырех чисел, каждое из которых – ноль или единица. Первое из них есть результат применения логической операции в случае, если оба аргумента нули, второе – результат в случае, если первый аргумент ноль, второй единица, третье – результат в случае если первый аргумент единица, второй ноль, а четвертый – в случае, если оба аргумента единицы.
Выходные данные
Вывести результат применения заданной логической операции к изображениям в том же формате, в котором изображения заданы во входных данных.
Объявляем два булевых динамических массива под две пиксельные таблицы и один статический для таблицы истинности, вводим входные данные. Затем поочерёдно сравниваем соответствующие элементы массивов с помощью функции
my_operation, которая принимает две переменные
a и
b булевского типа и булев массив
res с таблицей истинности, и возвращает соответствующее значение из таблицы для комбинации значений
a и
b. Результат сравнения выводим.
Весна… Прекрасное время! Все, казалось бы оживает и двигается, расцветает, начинается новый проход цикла жизни. И общеизвестный Мурзик не является исключением! Но если он чрезвычайно активен днем – то точно так же крепко спит ночью. Причем несчастный хищник видит преимущественно кошмары…
Одной ночью ему приснилось, что он судья на математических соревнованиях крыс (да, в наш век цифровых технологий даже крысы не остаются за гранью научно-технического прогресса). Соревнования проводятся среди [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-битовые знаковые числа.
Выходные данные
Номер команды, выигравшей соревнования. Если несколько команд имеют одинаковые результаты, то побеждает та, у которой больше номер.
Произведение результатов крыс может быть очень большим числом. Поэтому можно сравнивать их по знаку, если же по знаку они равны, то можно сравнивать не сами числа, а логарифмы от чисел. Создаем структуру, которая реализует эту идею.
Пусть даны две прямоугольные матрицы $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$.
// Проверяем возможность вычисления произведения матриц
if(ma!=nb){
cout<<-1;
return0;
}
int**b=newint*[nb];
for(inti=0;i<nb;i++){
b[i]=newint[mb];
}
for(inti=0;i<nb;i++){
for(intj=0;j<mb;j++){
cin>>b[i][j];
}
}
int**c=newint*[na];
for(inti=0;i<na;i++){
c[i]=newint[mb];
}
// Вычисляем произведение
for(inti=0;i<na;i++){
for(intj=0;j<mb;j++){
for(intr=0;r<ma;r++){
c[i][j]+=a[i][r]*b[r][j];
}
}
}
// Выводим результат
cout<<na<<" "<<mb<<"\n";
for(inti=0;i<na;i++){
for(intj=0;j<mb;j++){
cout<<c[i][j];
if(j+1!=mb)cout<<" ";
}
cout<<"\n";
}
return0;
}
Решение
Для начала, считываем данные матрицы $A$ из входного потока и записываем их в двумерный динамический массив. Далее, получив данные о размерности второй матрицы, мы можем определить, выполнима ли операция умножения, и если нет, то прервать выполнение программы. Если операция умножения данных матриц выполнима, то считываем и записываем данные второй матрицы, после чего, по приведённой выше формуле вычисляем произведение матриц $C = A \times B.$ Наконец, выводим полученную матрицу $C.$
Дан массив [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
Код программы
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
usingnamespacestd;
intmain(){
intn,m;
cin>>n>>m;
int**x=newint*[n];
for(inti=0;i<n;i++)
x[i]=newint[m];
for(inti=0;i<n;i++)
for(intj=0;j<m;j++)
cin>>x[i][j];
cout<<m<<" "<<n;
cout<<endl;
for(intj=0;j<m;j++){
for(inti=n-1;i>=0;i--)
cout<<x[i][j]<<" ";
cout<<endl;
}
return0;
}
Решение задачи:
Алгоритм решения данной задачи состоит в том, чтоб при выводе матрицы, начать выводить ее элементы не по строкам, а по столбцам, снизу вверх, начиная с первого столбца (левого нижнего угла матрицы).
Дан список мин. Требуется составить поле для игры в сапер.
Входные данные
Даны числа $N$ и $M$ (целые, положительные, не превышают $32$) — количество строк и столбцов в поле соответственно, далее число $W$ (целое, неотрицательное, не больше $100$) — количество мин на поле, далее следует $W$ пар чисел, координаты мины на поле (первое число — строка, второе число — столбец).
Выходные данные
Требуется вывести на экран поле. Формат вывода указан в примере.
Для хранения координат мин будем использовать двумерный массив. Все ячейки массива, используемые под поле, и их окружающие следует заблаговременно обнулить, чтобы получить точное количество мин при подсчете.
Теодор реализует новую стратегию игры «Оборона Царства». На каждом уровне игрок защищает королевство, которое представлено прямоугольной сеткой ячеек. В некоторых клетках игрок строит арбалетные башни. Башня защищает все клетки в той же строке и том же столбце. Никакие две башни не находятся на одной строке или столбце.
Штрафом положения является количество клеток в крупнейшем незащищенном прямоугольнике. Например, положение, показанное на рисунке имеет штраф [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
Код программы:
Код программы
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <algorithm>
usingnamespacestd;
intmain(){
intx_max,y_max,n,a=0,b=0;
cin>>x_max>>y_max>>n;
int*x=newint[n+2];
int*y=newint[n+2];
for(inti=1;i<n+1;i++)
cin>>x[i]>>y[i];
x[0]=y[0]=0;
x[n+1]=x_max+1;
y[n+1]=y_max+1;
sort(x,x+n+1);
sort(y,y+n+1);
for(inti=0;i<n+1;i++){
if(x[i+1]-x[i]>a)a=x[i+1]-x[i];
if(y[i+1]-y[i]>b)b=y[i+1]-y[i];
}
cout<<(a-1)*(b-1);
return0;
}
Решение задачи:
Алгоритм решения задачи состоит в том, чтобы найти максимальное количество незащищенных клеток между соседними башнями по координатам абсцисс и ординат (которые будет на [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] находим площадь самого большого незащищенного прямоугольника, которая равна количеству клеток в нем, что и является ответом задачи.
Имеется строка [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++
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <string>
usingnamespacestd;
int**answers;
strings;
intcalculate(intl,intr){
if(l>r)return0;//Если индекс левой границы отрезка больше индекса правой.
if(answers[l][r]==-1){//Если ответ для данного отрезка ещё не известен, находим его.
Идея решения состоит в том, чтобы разбить строку на меньшие по длине подстроки и найти ответ на задачу для каждой из них. Для хранения строки используется переменная
s, а ответы на подзадачи содержатся в двумерном массиве целых чисел
answers. В
answers[i][j] находится ответ для подстроки с
i-ого по
j-й символ включительно. В функции
main сначала вводится строка
s. Далее ширина и глубина массива
answers устанавливаются равными длине
s. После этого он заполняется начальными значениями. Значение [latex]-1[/latex] означает, что ответ для этой ячейки ещё не был найден. Однако очевидно, что если строка состоит ровно из одного символа, согласно условию задачи, его придётся удалить, значит, главную диагональ можно сразу заполнить единицами. Затем происходит вызов рекурсивной функции
calculate, принимающей индексы левой и правой границ целевой подстроки. Первый раз она вызывается для всей строки от первого до последнего символа. Работает эта функция следующим образом: если индекс левой границы отрезка больше индекса правой, что, в случае данной задачи, не имеет смысла, она возвращает ноль. Иначе она возвращает ответ на задачу для данной подстроки, а если этого не делалось ранее, то предварительно находит его. Происходит это так: сначала значение ответа устанавливается равным длине подстроки, поскольку в худшем случае необходимо будет удалить её всю целиком. Если символы на концах подстроки одинаковые, они, как сказано в условии, будут удалены в дальнейшем, потому нужно рассматривать минимум из текущего значения ответа и ответа для подстроки без крайних символов. Однако может оказаться, что выгоднее удалить символы из каких-то двух меньших подстрок, потому далее в цикле рассматриваются все возможные комбинации двух подстрок, из которых можно составить конкатенацией текущую. В итоге получаем ответ на задачу для данной подстроки.
Имея два двумерных массива [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]. Вывод должен строго соответствовать формату, приведенному в примере. Если существует несколько оптимальных порядков перемножения матриц, выведите любой из них.
Пусть [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] матриц. Затем, рекурсивно восстановим оптимальный порядок умножения матриц. Для вывода ответа в соответствующем формате также воспользуемся рекурсией.
С помощью [latex]x_{ij}, i=1,2; j=1,\ldots,n.[/latex] — действительной матрицы на плоскости задано n точек так, что [latex]x_{1j}, x_{2j}[/latex] — координаты [latex]j[/latex] — точки. Точки попарно соединены отрезками. Найти длину наибольшего отрезка.
Находим длину наибольшего отрезка.
С помощью вложенных циклов мы находим длины всех отрезков по формуле
[latex] AB=\sqrt{(x_{2}-x_{1})^{2}+(y_{2}-y_{1})^{2}}, A(x_{1},y_{1}), B(x_{2},y_{2}). [/latex]
По алгоритму нахождения максимума находим длину наибольшего отрезка.
Задача. Указать маршрут коня. Начинающегося на одном заданном поле шахматной доски и оканчивающемся на другом. Никакое поле не должно встречаться в маршруте дважды.
Читаем входные данные. Преобразуем их в координаты начального и финального поля на шахматной доске. Массив chessboard сначала заполняем -1 (не пройденные поля), затем значение в поле с начальными координатами присваиваем 0. Затем будем отмечать все доступные ходы коня до тех пор пока не изменится значение в финальном поле. Затем, если у нас не совпали начальное и финальное поле будем восстанавливать путь коня. Создаем массив в котором и будет путь коня. Первое значение которое мы заносим в массив будет наше финальное поле. Затем с этого поля будем рассматривать все возможные ходы которые пройдут по уже помеченным клеткам. Если в финальное поле можно было попасть несколькими путями одинаковой длины то нам не имеет значение каким из них возвращаться в начальное поле. Затем выводим массив пути в обратном порядке.
Дана квадратная матрица порядка [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]), а во втором цикле уже организовать вывод и вычисление собственно результирующего вектора.
Задача:
Даны натуральные числа 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].
Идея решения:
Считать n, m как целочисленные переменные. После этого считать r как переменную типа double. Следующим считать массив nxm созданный благодаря генератору матриц из случайных чисел заданного размера. Завести переменную [latex]sum = 0[/latex] для хранения результата. Проверять построчно каждый столбик на наличие положительного числа и прибавить первое положительное число в строке, умноженное на [latex]{r}^{n-i-1}[/latex], к результаты. В случает отсутствия положительного элемента в строке, брать 0.5. В конце вывести результат.
Суммы по косой. Просуммировать элементы матрицы [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
Код программы:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
usingnamespacestd;
intmain()
{
intt;
cin>>t;
constintn=t;
inta[n][n];
intb[2*n-1];
for(inti=0;i<2*n-1;i++)
b[i]=0;
for(inti=0;i<n;i++)
{
for(intj=0;j<n;j++)
{
cin>>a[i][j];
cout<<a[i][j]<<" ";
}
cout<<"\n";
}
for(inti=0;i<n;i++)
for(intj=0;j<n;j++)
{
b[i-j+n-1]+=a[i][j];
}
for(inti=2*n-2;i>=0;i--)
cout<<b[i]<<" ";
return0;
}
Сначала вводим размер квадратной матрицы — [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].
Дана действительная квадратная матрица порядка [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++):
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
usingnamespacestd;
intmain(){
intn;
cin>>n;
double**m;
m=newdouble*[n];
for(inti=0;i<n;i++)m[i]=newdouble[n];
double**m1;
m1=newdouble*[n-1];
for(inti=0;i<n-1;i++)m1[i]=newdouble[n-1];
for(inti=0;i<n;i++){
for(intj=0;j<n;j++){
cin>>m[i][j];
}
}
inti0,j0;
cin>>i0>>j0;
for(inti=0,tr=0;tr<n-1;){
if(i!=i0-1){
for(intj=0,td=0;td<n-1;j++,td++){
if(j==j0-1)j++;
m1[tr][td]=m[i][j];
}
i++;
tr++;
}
elsei++;
}
delete[]m;
m=m1;
for(inti=0;i<n-1;i++){
for(intj=0;j<n-1;j++){
printf("%5.3lf\t",m[i][j]);
}
cout<<endl;
}
return0;
}
Java:
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
importjava.util.*;
importjava.lang.*;
importjava.io.*;
classIdeone{
publicstaticvoidmain(String[]args){
Scanner in=newScanner(System.in);
intn;
n=in.nextInt();
double[][]m=newdouble[n][n];
double[][]m1=newdouble[n-1][n-1];
for(inti=0;i<n;i++){
for(intj=0;j<n;j++){
m[i][j]=in.nextDouble();
}
}
inti0,j0;
i0=in.nextInt();
j0=in.nextInt();
for(inti=0,tr=0;tr<n-1;){
if(i!=i0-1){
for(intj=0,td=0;td<n-1;j++,td++){
if(j==j0-1)j++;
m1[tr][td]=m[i][j];
}
i++;
tr++;
}
elsei++;
}
m=m1;
for(inti=0;i<n-1;i++){
for(intj=0;j<n-1;j++){
System.out.print(m[i][j]+" ");
}
System.out.println();
}
}
}
Сначала пользователю предлагается ввести порядок матрицы, затем элементы этой матрицы. После чего, по условию задачи, пользователь должен задать [latex]i[/latex]-строку и [latex]j[/latex]-столбец, которые программа должна изъять из матрицы.
Протестировать программу можно здесь (C++) и здесь (Java).
Задача Ю4.27. Сессия. Результаты сессии, состоящей из трёх экзаменов, для группы из [latex]n[/latex] студентов представлены матрицей [latex]K \left(n,3 \right)[/latex]. Оценка ставится по четырёхбалльной системе; неявка обозначена единицей. Подсчитать количество неявок, неудовлетворительных, удовлетворительных, хороших и отличных оценок по каждому экзамену.
Изначально пользователю предлагается ввести количество студентов [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).
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 — это индексы двух узлов, между которыми мы хотим заблокировать переход. Если между ними нет связи, возникает ошибка. В конце строки обязательно должен стоить символ перехода на новую строку.
Программа:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
usingnamespacestd;
intmain()
{
intN;//Количество узлов, включая шлюзы
intL;//Количество связей
intE;//Количество шлюзов
cin>>N>>L>>E;cin.ignore();
intN1[L][2];// Массив для связей
for(inti=0;i<L;i++){
cin>>N1[i][0]>>N1[i][1];cin.ignore();
}
intEI[E];// Индексы шлюзов
for(inti=0;i<E;i++){
cin>>EI[i];cin.ignore();
}
// Алгоритм сортировки (его достаточно)
for(inti=0;i<L;i++){
for(intk=0;k<E;k++){
if(N1[i][1]==EI[k])swap(N1[i][1],N1[i][0]);
}
}
// игровой цикл
while(1){
intSI;//Индекс связи, на которой находится Агент
cin>>SI;cin.ignore();
boolAgentIsNear=false;//Агент возле шлюза!
for(inti=0;i<L;i++){
boolT=false;//Для прерывания цикла
for(intk=0;k<E;k++){
if(EI[k]==N1[i][0]&&SI==N1[i][1]){
cout<<EI[k]<<' '<<SI<<endl;
N1[i][0]=-1;
AgentIsNear=true;
T=true;
break;
}
}
if(T)break;
}
if(!AgentIsNear){
for(inti=0;i<L;i++){
boolT=false;//Для прерывания цикла
for(intk=0;k<E;k++){
if(N1[i][0]==EI[k]){
cout<<EI[k]<<' '<<N1[i][1]<<endl;
N1[i][0]=-1;
T=true;
break;
}
}
if(T)break;
}
}
}
}
Идея решения: Всё предельно просто: Если агент находится вблизи одного из шлюзов, закрываем переход между агентом и этим шлюзом. Иначе закрываем переход между шлюзом и ближайшим узлом.
Переходы между узлами занесены в двумерный массив N1, далее этот массив был своеобразно отсортирован (для удобства). В игровом цикле объявляем булевую переменную AgentIsNear — агент вблизи шлюза.
Первый цикл: Проверяем каждую клетку вокруг каждого шлюза на присутствие там агента. И если он таки там есть, блокируем переход, меняем первую переменную (отвечающую за шлюз) в массиве переходов (N1) на -1 (значение, которое никогда не встретится), изменяем AgentIsNear на true и прерываем цикл.
Второй цикл: так как агент гуляет где-то далеко, то мы блокируем любой свободный проход любого шлюза.
Второй цикл выполняется только тогда, когда за весь первый цикл условие внутри него ни разу не стало истинным.
Программа проходит все тесты на MEDIUM и, что удивительно, половину тестов на HARD! Взято с CodinGame
