A711б

Задача:

Дана матрица [latex]A[/latex] размера [latex]m\times n[/latex]. Найти матрицу [latex]AA^{*}[/latex] (её размер [latex]m\times m[/latex]).

[latex]m[/latex] [latex]n[/latex] [latex]A[/latex] [latex]AA^{*}[/latex]
3 5 1 2 3 4 5
0 0 0 78 92
6 7 8 9 110
55 772 630
772 14548 10822
630 10822 12330
Тест пройден
2 4 11 22 33 44
76 0 1 0
3630 869
869 5777
Тест пройден

C++:

Java:

[latex]A^{*}[/latex] — транспонированная матрица [latex]A[/latex]. Её строки — это столбцы [latex]A[/latex], а столбцы — строки [latex]A[/latex].

Задача на Ideone:
C++
Java

e-olymp 1061. Покраска лабиринта

Задача e-olimp 1061.

Лабиринт представляет собой квадрат, состоящий из N×N сегментов. Каждый из сегментов может быть либо пустым, либо заполненным камнем. Гарантируется, что левый верхний и правый нижний сегменты пусты. Лабиринт обнесен снизу, сверху, слева и справа стенами, оставляющими свободными только левый верхний и правый нижний углы. Директор лабиринта решил покрасить стены лабиринта, видимые изнутри.  Помогите ему рассчитать количество краски, необходимой для этого.

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

В первой строке находится число N, затем идут N строк по N символов: точка обозначает пустой сегмент, решетка — сегмент со стеной.

3N33, размер сегмента 3×3, высота стен 3 метра.

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

Вывести одно число — площадь видимой части внутренних стен лабиринта в квадратных метрах.

Пример

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

. . . . .

. . . # #

. . # . .

. . # # #

. . . . .

198

C++:

Java:

Для решения задачи я использовала алгоритм поиска в ширину: начиная с левой верхней клетки, которая гарантированно пуста, проверяю все смежные с ней и заношу их в план проверки. Для каждой клетки считаю количество пустых смежных клеток и получаю число стен рядом с ней. Чтобы было удобно проверять смежные клетки на пустоту, я сделала «стену» вокруг данного лабиринта. После проверки клетки отмечаю, что она просмотрена.

Так как в условии не гарантируется, что есть проход от левой верхней до правой нижней клетки, проверяю, посещена ли последняя. Если нет, снова запускаю поиск, начиная с неё.

Засчитанное решение.

Задача на Ideone:
C++
Java

AA27

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

[latex]s1[/latex] [latex]s2[/latex] Комментарий
qwerty qwertqwy Тест пройден
_ qwert y _ qwert _ y Тест пройден
qwe Невозможно выполнить операцию.

C++:

Java:

Дана строка [latex]s1[/latex]. Переписываем из неё в строку [latex]s2[/latex] все символы, кроме последнего. Добавляем первый, второй и последний символ строки [latex]s1[/latex] в строку [latex]s2[/latex].

Задача на Ideone:
C++
Java

Ю12.43

Задача: Для двух заданных строк символов найти самую длинную общую подстроку. Пробелы и знаки препинания игнорировать, строчные и прописные буквы считать неразличимыми. Например, строки: «Дай вилку! Бок севрюжий кончается» и «Чемпионский кубок достался не нам» содержат общую подстроку «кубок».

Строка а Строка b  Результат Комментарий
Q_+wer ty q!w ert) q qwert Тест пройден
`Curiouser and curiouser!’ cried Alice (she was so much surprised, that for the moment she quite forgot how to speak good English); `now I’m opening out like the largest telescope that ever was! Good-bye, feet!’ (for when she looked down at her feet, they seemed to be almost out of sight, they were getting so far off). `Oh, my poor little feet, I wonder who will put on your shoes and stockings for you now, dears?

 

tfor good Тест пройден
Qwe^r ty qwE r!ty qwerty  Тест пройден

C++:

Java:

Даны строки [latex]a[/latex] и [latex]b[/latex]. Сначала переписываем их в строки [latex]a2[/latex] и [latex]b2[/latex], при этом избавляясь от всех символов, кроме букв, и понижая их регистр.

Чтобы выделить все совпадающие комбинации букв, сравниваем каждый символ из [latex]a2[/latex] подряд со всеми символами из  [latex]b2[/latex]. Когда находим одинаковые буквы, проверяем уже следующий символ в [latex]a2[/latex] и в  [latex]b2[/latex]. Все общие подстроки записываем в строку  [latex]c[/latex] через пробел.

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

Задача на Ideone:
C++
Java

Ю11.8

Метод Симпсона.  Вычислить определённый интеграл [latex]I=\int_{a}^{b}{f\left(x \right)}dx[/latex] по формуле Симпсона: [latex]I\approx \frac{b-a}{6n}\left(y_{0}+4y_{1}+2y_{2}+\cdot \cdot \cdot +4y_{2n-1}+y_{2n} \right)[/latex], где [latex]2n[/latex] — количество отрезков разбиения, [latex]y_{0}[/latex], [latex]y_{1}[/latex], …, [latex]y_{2n}[/latex] — значение функции [latex]f\left(x \right)[/latex] на концах отрезков.
В задачах на численное интегрирование определённый интеграл требуется найти с заданной точностью, для чего вычисление по формуле метода рекомендуется проводить многократно, каждый раз уменьшая шаг интегрирования в два раза, пока разница между соседними приближениями не станет меньше заданной погрешности.

Функция [latex]a[/latex] [latex]b[/latex] [latex]eps[/latex] Интеграл Комментарий
[latex]f\left(x \right)=\sin \left(x^{2}+2x \right)[/latex] 1 3 0.0001 -0.143058 Тест пройден.
[latex]\ln \left(1+x \right)[/latex] 1 3 0.0001 2.15888 Тест пройден.
[latex]\tan \left(3x^{3} \right)[/latex] 2 15 0.01 0.0256033 Тест пройден.
[latex]x\left( x^{2}-1\right)\left(x+1 \right)[/latex] -1 1 0.3 -0.265625 Тест пройден.

C++:

Java:

С помощью программы можно вычислить интеграл любой непрерывной на  [latex]\left[a;b \right][/latex]  функции, для этого нужно изменить 7 строку.

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

Задача на Ideone:
C++
Java

А394а

Задача:  Дана целочисленная квадратная матрица порядка [latex]n[/latex]. Найти номера строк, все элементы которых — нули.

[latex]n[/latex] [latex]M[/latex] [latex]v[/latex] Комментарий
4
0 0 0 0
0 -290 56 48
0 0 0 0
1 2 3 4
1 3
3
0 0 0
0 0 0
0 0 0
1 2 3
3
1 2 3
4 5 6
7 8 9
Таких строк нет.

C++:

Java:

Пусть дана квадратная матрица [latex]M[/latex], количество строк и столбцов — [latex]n[/latex].

Заводим дополнительную переменную [latex]k[/latex]. При вводе элементов матрицы, проверяем, равны ли они нулю. Если элемент равен нулю, прибавляем к значению [latex]k[/latex] единицу. При первом ненулевом элементе переходим к другой строке. Если после прочтения строки [latex]k=n[/latex], то все элементы строки были нулевыми (перед прочтением каждой новой строки в [latex]k[/latex] записывается ноль). Записываем номер строки в заранее созданный вектор [latex]v[/latex]. Выводим элементы вектора, увеличивая их на единицу, чтобы получилась правильная нумерация строк.

Задача на Ideone:
C++
Java