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

Ю4.10

Задача: Найти среднее арифметическое элементов каждой строки матрицы [latex]Q\left(l,m \right)[/latex] и вычесть его из элементов этой строки.

[latex]l[/latex] [latex]m[/latex] [latex]Q\left(l,m \right)[/latex] [latex]\acute{Q}\left(l,m \right)[/latex]
2 3
4 6 2
5 9 10
0 2 -2
-3 1 2
4 3
-5 -2 -3
6 5 0
-8 9 -64
468 -3 1
-1.66667 1.33333 0.333333
2.33333 1.33333 -3.66667
13 30 -43
312.667 -158.333 -154.333
1 1 8 0

C++:

Java:

У переменных [latex]l[/latex], [latex]m[/latex] (количество строк и столбцов соответственно) — тип int, т.к. это целые числа.
Массив для данной матрицы [latex]q\left[l \right]\left[m \right][/latex] и массивы элементов суммы [latex]sum\left[l \right][/latex] и среднего арифметического [latex]sr\left[l \right][/latex] каждой строки  имеют тип double, так как могут содержать вещественные числа.

В первом цикле инициализируем элементы массива [latex]sum\left[l \right][/latex] нулями, чтобы там не лежал мусор.

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

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

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

Ю1.8

Задача: Среднегодовая производительность труда. За первый год производительность труда на предприятии возросла на [latex]p_{1}[/latex]%, за второй и третий — соответственно на [latex]p_{2}[/latex]% и [latex]p_{3}[/latex]%. Найти среднегодовой прирост производительности (в процентах).

[latex]p_{1}[/latex]% [latex]p_{2}[/latex]% [latex]p_{3}[/latex]% sp%
15 30 50 30.8913
5 5 5 5
-10 60 45 27.8135
0 0 0 0

C++:

Java:

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

Сначала найдем общий прирост за 3 года (обозначен переменной [latex]op[/latex]), воспользовавшись  формулой:

[latex]p_{\Sigma }=\left(1+\frac{p_{1}}{100} \right)\left(1+\frac{p_{2}}{100} \right)\left(1+\frac{p_{3}}{100} \right)[/latex]

Тогда для того, чтобы найти среднегодовой прирост за 3 года (обозначен переменной [latex]sp[/latex]), надо извлечь корень третьей степени из общего прироста.

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

А136л

Задача: Даны натуральное число [latex]n[/latex], действительные числа [latex]a_{1},\cdot \cdot \cdot ,a_{n}[/latex]. Вычислить: [latex]\sqrt{\left|a_{1}a_{2}\cdot \cdot \cdot a_{n} \right|}[/latex].

[latex]n[/latex] [latex]a_{1}[/latex] [latex]a_{2}[/latex] [latex]a_{3}[/latex] [latex]a_{4}[/latex] [latex]a_{5}[/latex] [latex]a_{6}[/latex] [latex]a_{7}[/latex] [latex]a_{8}[/latex] [latex]k[/latex]
4 -5 2 4 -3.6 12
8 -5 0.2 -3.2 0.5 -1.25 20 2 80 80
3 4 4 0 0
5 3 8 6 2.8 1.3 22.894541

С++:

Java:

Объявляем переменную [latex]n[/latex] (количество элементов — это целое число, поэтому используем тип int) и переменные a (элементы произведения), p (произведение), k (корень из модуля произведения элементов), они могут быть вещественными, поэтому выбираем тип double.

В цикле for считываются элементы [latex]a_{1},a_{2},\cdot \cdot \cdot ,a_{n}[/latex], где [latex]i[/latex] — индекс элемента, и вычисляется их произведение.

После цикла вычисляется корень из модуля произведений элементов.

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

Ю3.27

Задача:  Численно убедиться в справедливости равенства, для чего для заданного значения аргумента [latex]x[/latex] вычислить левую его часть и разложение, стоящее в правой части с заданной погрешностью [latex]\varepsilon [/latex]. Испытать разложение на сходимость при разных значениях аргумента, найти скорость сходимости, для чего вывести число итераций [latex]n[/latex] (слагаемых или сомножителей), необходимых для достижения заданной точности. В некоторых задачах указан интервал допустимых значений аргумента [latex]x[/latex], при которых сходимость гарантируется.

[latex]\ln \left(1-x \right)=-\left(x+\frac{x^{2}}{2}+\frac{x^{3}}{3}+\cdot \cdot \cdot +\frac{x^{n}}{n}+\cdot \cdot \cdot \right)[/latex],   [latex]x<1[/latex]

[latex]x[/latex] [latex]eps[/latex] Левая часть Правая часть Количество шагов
0.1 0.001 -0.105361 -0.105 3
0.1 0.000001 -0.105361 -0.105360 6
0.5 0.001 -0.693147 -0.692262 8
0.5 0.000001 -0.693147 -0.693146 17
0.95 0.001 -2.995732 -2.994775 101
0.95 0.000001 -2.995732 -2.995731 222

C++:

Java:

Для переменных [latex]x, eps, a, b, c[/latex] я использовала double, так как [latex]x<1[/latex] и [latex]eps[/latex] ([latex]\varepsilon [/latex]) — вещественные числа, которые вводит пользователь, [latex]a, b, c[/latex] используются для вычислений, поэтому тоже вещественные. Для переменной [latex]n[/latex] (в неё записывается количество шагов цикла) я использовала тип int, т.к. это целые числа.

Сперва вычисляем значение переменной [latex]a[/latex] — левую часть равенства.

Для вычисления правой части используем цикл for, который работает пока [latex]\left|a-b \right|\geq eps[/latex] (т.е. различие между правой и левой частью больше, чем погрешность, заданная пользователем).
При каждом шаге переменная [latex]n[/latex] увеличивается на единицу для подсчёта скорости сходимости.
Переменная [latex]c[/latex] обозначает элемент суммы, а [latex]b[/latex] — сумму элементов в правой части равенства.

Эта задача на Ideone:
C++
Java

Ю1.27

Задача: Треугольник задаётся координатами своих вершин на плоскости: [latex]A\left(x_{1};y_{1} \right), B\left(x_{2};y_{2} \right), C\left(x_{3};y_{3} \right)[/latex] . Найти точку [latex]D[/latex], симметричную точке [latex]A[/latex] относительно стороны [latex]BC[/latex].

[latex]a_{x}[/latex] [latex]a_{y}[/latex] [latex]b_{x}[/latex] [latex]b_{y}[/latex] [latex]c_{x}[/latex] [latex]c_{y}[/latex] [latex]d_{x}[/latex] [latex]d_{y}[/latex]
2 2 0 0 1 0 2 -2
-4 5 -2 3 -2 2 0 5
-3 -3 -4 -1 -1 -4 -2 -2
5 2 3.5 1 4.5 4 2.9 2.7

C++:

Java:

Для всех переменных ([latex]a_{x}[/latex], [latex]a_{y}[/latex], [latex]b_{x}[/latex], [latex]b_{y}[/latex], [latex]c_{x}[/latex], [latex]c_{y}[/latex] — координаты точек [latex]A, B, C[/latex], даны по условию; [latex]d_{x}[/latex], [latex]d_{y}[/latex] — координаты точки [latex]D[/latex] — нужно найти) я использовала тип double, так как они могут быть вещественными числами.

Найдём уравнение прямой [latex]BC[/latex] по формуле [latex]\frac{\left(x-x_{1} \right)}{\left(x_{2}-x_{1} \right)}=\frac{\left(y-y_{1} \right)}{\left(y_{2}-y_{1} \right)}[/latex]. Подставляем значения: [latex]\frac{\left(x-b_{x} \right)}{\left(c_{x}-b_{x} \right)}=\frac{\left(y-b_{y} \right)}{\left(c_{y}-b_{y} \right)}[/latex]. Приводим к виду: [latex]x\left(c_{y}-b_{y} \right)-y\left(c_{x}-b_{x} \right)+b_{y}\left(c_{x}-b_{x} \right)-b_{x}\left(c_{y}-b_{y} \right)=0[/latex].
Переменными [latex]A_{1}[/latex],  [latex]B_{1}[/latex],  [latex]C_{1}[/latex]  я обозначила постоянные при [latex]x, y[/latex] и свободный член, чтобы уравнение приняло вид: [latex]A_{1}\cdot x+B_{1}\cdot y+C_{1}=0[/latex].

Проведём прямую через точку [latex]A[/latex] перпендикулярно прямой [latex]BC[/latex]. Составим её уравнение по формуле: [latex]A\left(y-a_{y} \right)-B\left(x-a_{x} \right)=0[/latex]. Получим: [latex]A_{1}\cdot y-B_{1}\cdot x+B_{1}\cdot a_{x}-A_{1}\cdot a_{x}=0[/latex].  Аналогично для постоянных в этом уравнении я использовала переменные [latex]A_{2}[/latex],  [latex]B_{2}[/latex],  [latex]C_{2}[/latex]. Соответственно, [latex]A_{2}=-B_{1}[/latex],   [latex]B_{2}=A_{1}[/latex],   [latex]C_{2}=B_{1}\cdot a_{x}-A_{1}\cdot a_{y}[/latex].

Теперь найдём точку пересечения этой прямой и прямой  [latex]BC[/latex] — точку [latex]O\left(o_{x};o_{y} \right)[/latex]. Получим: [latex]o_{x}=\frac{B_{1}\cdot C_{2}-B_{2}\cdot C_{1}}{A_{1}\cdot B_{2}-A_{2}\cdot B_{1}}[/latex]   и   [latex]o_{y}=\frac{C_{1}\cdot A_{2}-C_{2}\cdot A_{1}}{A_{1}\cdot B_{2}-A_{2}\cdot B_{1}}[/latex].

Так как точка [latex]D[/latex] симметрична точке [latex]A[/latex] относительно [latex]BC[/latex], и [latex]AD[/latex] пересекается с [latex]BC[/latex] в точке [latex]O[/latex]: точка [latex]O[/latex] — середина [latex]AD[/latex]. Из формулы координаты середины отрезка (  [latex]o_{x}=\frac{a_{x}+d_{x}}{2}[/latex] и [latex]o_{y}=\frac{a_{y}+d_{y}}{2}[/latex]  ) находим [latex]d_{x}=2\cdot o_{x}-a_{x}[/latex]  и  [latex]d_{y}=2\cdot o_{y}-a_{y}[/latex].

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

А114в

Задача: Вычислить [latex]\sum_{i=1}^{10}{\frac{1}{i!}}[/latex].

Ответ
1.718282

C++:

Java:

Для переменных [latex]a, b[/latex] я использовала тип double, так как они они используются для вычислений и являются вещественными числами. Для переменной [latex]i[/latex] — тип int, так как [latex]i[/latex] — это целые числа от 1 до 10.

Чтобы решить задачу, воспользуемся циклом for, который работает при [latex]1\leq i\leq 10[/latex] и каждый раз прибавляет к [latex]i[/latex] единицу. Переменную [latex]i[/latex] я объявила в цикле, так как вне цикла она не нужна.

Сначала найдём [latex]a[/latex] — элемент суммы, который зависит от выбранного [latex]i[/latex]. После сложим [latex]a[/latex] и переменную [latex]b[/latex], которая обозначает сумму предыдущих элементов, a результат запишем снова в переменную [latex]b[/latex].

Когда цикл дойдёт до 11, его условие перестанет выполняться и напечатается последнее значение, присвоенное переменной [latex]d[/latex].

Эта задача на Ideone:
C++
Java

Ю2.4

Задача: Числа [latex]a, b, c[/latex] тогда и только тогда являются сторонами треугольника, когда существуют такие положительные [latex]x, y, z[/latex], что:

[latex]\begin{cases}& \text{ } a=x+y \\& \text{ } b=y+z \\& \text{ } c=x+z\end{cases}[/latex]

[latex]a[/latex] [latex]b[/latex] [latex]c[/latex] [latex]x[/latex] [latex]y[/latex] [latex]z[/latex] Комментарий
10 5 7 6 4 1 Выполняется
3.5 6.8 4 0.35 3.15 3.65 Выполняется
-5 7 3  — Не треугольник
17 4 8  — Не треугольник

C++:

Java:

Для всех переменных ( [latex]a, b, c[/latex] — даны по условию, [latex]x, y, z[/latex] — нужно найти) я использовала тип данных double, так как числа могут быть вещественными.

[latex]a, b, c[/latex] — стороны треугольника, поэтому они не могут быть отрицательными. И по соотношениям между сторонами треугольника каждая сторона меньше суммы двух других сторон. В противном случае [latex]a, b, c[/latex] не являются сторонами треугольника.

Чтобы получить значения [latex]x, y, z[/latex], решаем систему, данную в условии. Из первого уравнения: [latex]x=a-y[/latex]. Из второго: [latex]z=b-y[/latex]. Подставляем [latex]x=a-y[/latex] и [latex]z=b-y[/latex] в третье уравнение: [latex]c=a+b-2\cdot y[/latex]. Находим [latex]y=\frac{a+b-c}{2}[/latex], [latex]x=a-y[/latex], [latex]z=b-y[/latex].

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

А59е

Задача А59е. Даны действительные числа [latex]x[/latex], [latex]y[/latex]. Определить, принадлежит ли точка [latex]x[/latex], [latex]y[/latex] заштрихованной части плоскости.

A59е

Значение  [latex]x[/latex] Значение [latex]y[/latex] Комментарий
0 0 Принадлежит фигуре.
-2 0 Принадлежит фигуре.
0 1 Принадлежит фигуре.
1 0 Принадлежит фигуре.
0 -1 Принадлежит фигуре.
-2 1 Не принадлежит фигуре.
-2 -0.5 Принадлежит фигуре.
1 -1 Не принадлежит фигуре.
0.5 0.5 Принадлежит фигуре.

С++:

Java:

Если точка [latex]D[/latex] лежит справа от оси [latex]OY[/latex], ищем расстояние от неё до точки [latex]O\left(0,0 \right)[/latex]. Если оно меньше либо равно [latex]1[/latex], точка [latex]D[/latex] принадлежит полукругу.

Если точка [latex]D[/latex] лежит слева от оси [latex]OY[/latex], будем проводить прямые через каждые две вершины треугольника [latex]ABC[/latex], где [latex]A\left(-2,0 \right)[/latex], [latex]B\left(0,1 \right)[/latex], [latex]C\left(1,0 \right)[/latex].

Воспользуемся уравнением прямой:
[latex]\left ( x-x_{A} \right )\left ( y_{B}-y_{A} \right )-\left ( y-y_{A} \right )\left ( x_{B}-x_{A} \right )=0[/latex]

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

Функция dotLine определяет положение точки относительно прямой: она вычисляет значение в уравнении прямой и определяет, к какой части плоскости относится точка.

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

Функция dotDot определяет, расположены ли точки в одной части плоскости.

Если уравнение прямой даст 0, то точка [latex]D[/latex] лежит на прямой и принадлежит треугольнику.

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