A713

Задача

Следом квадратной матрицы называется сумма элементов, расположенных на главной диагонали.

Даны квадратная матрица порядка m, натуральное число n. Вычислить следы матриц [latex]A, A^{2}, … , A^{n}[/latex].

Тесты

[latex]m[/latex] [latex]n[/latex] [latex]A[/latex] следы [latex]A, A^{2}, … , A^{n}[/latex] Комментарий
3 4  [latex]\begin{pmatrix} 1 & 2 & 3\\ 1 & 2& 3 \\ 1 & 2 & 3 \end{pmatrix}[/latex] 6 36 216 1296 Пройден
 2  5  [latex]\begin{pmatrix} 1 & 2\\ 3 & 4 \end{pmatrix}[/latex]  5 29 155 833 4475  Пройден
Код
C++

Java

Решение

 Находим след исходной матрицы вне цикла. После, в цикле перемножаем матрицы и находим следы уже полученных матриц.

Решение на ideone: (C++) (Java).

e-olimp 695. Range Variation Query

Задача e-olimp 695.

Последовательность [latex]a_{n}[/latex] задается следующей формулой: [latex]a_{n}=n^{2} mod 12345+n^{3} mod 23456[/latex].

Требуется много раз отвечать на запросы следующего вида:

  • найти разность между максимальным и минимальным значением среди элементов [latex]a_{i},a_{i+1}, …,a_{j}[/latex];
  • присвоить элементу [latex]a_{i}[/latex] значение [latex]j[/latex].

Технические условия.

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

Первая строка содержит натуральное число [latex]k (k\leq 100000)[/latex]  — количество запросов. Следующие [latex]k[/latex] строк содержат запросы, по одному в строке. Запрос номер [latex]i[/latex] описывается двумя целыми числами [latex]x_{i},y_{i}[/latex].

Если [latex]x_{i}>0[/latex], то требуется найти разность между максимальным и минимальным значением среди элементов [latex]a_{x_{i}}…a_{y_{i}}[/latex]. При этом [latex]1\leq x_{i}\leq y_{i}\leq 100000[/latex].

Если [latex]x_{i}<0[/latex], то требуется присвоить элементу [latex]a_{-x_{i}}[/latex] значение[latex]y_{i}[/latex]. При этом[latex]-100000\leq x_{i}\leq 1[/latex] и [latex]\left | y_{i} \right |\leq 100000[/latex].

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

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

Пример.

Пример входных данных Пример выходных данных
7

1 3

2 4

-2 -100

8 9

-3 -101

2 3

34

68

250

234

1

 

Решение.

Так как количество запросов [latex]k\leq 100000[/latex] сначала считаем значение всех элементов последовательности и сохраняем их в массив. Если требуется найти разность между максимумом и минимумом,то находим их проверяя все элементы отрезка и выводим разность. Если требуется заменить  элемент, то заменяем соответствующий элемент последовательности на новый.

Ссылка на засчитанное решение.

Данный код на ideone.

В скором времени будет добавлено более эффективное решение с помощью дерева отрезков.

АА13

Задача.

В заданной строке поменять местами рядом стоящие символы между собой (1 и 2, 3 и 4 и т.д., для строки нечетной длины, последний символ не менять).

Тесты.

Ввод Вывод Комментарий
123456 214365 Пройден
abcde badce Пройден

Код.

Используя цикл, проходим по каждому второму символу строки и меняем его с предыдущим.

Данный код на ideone.

Ю12.34

Задача.

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

Тесты.

Ввод Вывод Комментарий
programming a in on go no an man am or arm air ring ago pain grin rain mom main among roar grip pair rip map nor aim iron program pin ma moan groan gang gain rag pig piano ramp gin ram rig Пройден
polymorphism is his him my so or room sir ship lip slip mom shop simply pop rip poor pool sip oil holy hip limp hop prop spy loom Пройден

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

Код(string).

Используем ввод как условие цикла while. Вводим вспомогательную строку temp, в которую записываем исходное слово. Символы строки temp, которые совпадают с символами данного слова из словаря, заменяем на точки (подходят любые символы, кроме английских букв), учитывая, таким образом, кратность вхождения. Также для проверки вводим логические переменные b1(содержатся ли все символы из строки dict в temp?) и b2(содержится ли j-ый символ из dict в temp?).

Данный код на ideone.

Код(c-string).

Решение аналогично.

Данный код на ideone.

А410г

Задача.

Дана целочисленная матрица [latex]\left[a_{ij} \right] {i,j=1, \ldots,n}[/latex]. Получить [latex]b_{1}, \ldots,b_{n}[/latex], где  [latex]b_{i}[/latex] — это  [latex]\sum_{j=1}^{n}{\left|a_{ji} \right|}[/latex].

Тесты.

n [latex]\left[a_{ij} \right][/latex] [latex]b_{1}, \ldots,b_{n}[/latex] Комментарий
2 [latex]\begin{pmatrix}1& 4\\-5 & 7\end{pmatrix}[/latex] 6 11 Пройден
3 [latex]\begin{pmatrix}1 & 2 & -3\\-4 & 5 & 6\\7 & -8 & 9\end{pmatrix}[/latex] 12 15 18 Пройден

Решение.

C++

Java

Вводим элементы матрицы. Используя цикл вычисляем  [latex]b_{i}[/latex]. После завершения вычислений, выводим элементы массива [latex]b[/latex] на экран.

Для выполнения программы и проверки тестов можно воспользоваться следующей ссылкой(C++) или другой(Java).

Ю4.16

Задача.

Все четные элементы целочисленного массива [latex]K(n)[/latex] поместить в массив [latex]L(n)[/latex], а нечетные — в массив [latex]M(n)[/latex]. Подсчитать количество тех и других.

Тесты.

n K[ ] num of L L[ ] num of M M[ ] Комментарий
6 1 2 3 4 5 6 3 2 4 6 3 1 3 5 Пройден
5 1 1 6 4 3 2 6 4 3 1 1 3 Пройден

Решение.

C++

Java

В цикле проверяем каждый элемент массива [latex]K(n)[/latex], если элемент четный, то добавляем его в массив [latex]L(n)[/latex], если нет, то добавляем его в массив [latex]M(n)[/latex]. При этом после каждого добавления увеличиваем соответствующий счетчик на 1.

Для выполнения программы и проверки тестов можно воспользоваться следующей ссылкой(C++) или другой(Java).

 

 

Ю3.22

Задача.

Для заданного [latex]x>1[/latex] вычислить [latex]y=\sqrt{x}[/latex] по итерационной формуле: [latex]y_{i}=\frac{1}{2}(y_{i-1}+\frac{x}{y_{i-1}})[/latex] c заданной погрешностью ε, задав начальное приближение [latex]y_{0}=x[/latex]. Сравнить с результатом использования встроенной функции. Сколько итераций пришлось выполнить?

Тесты.

x ε [latex]y_{i}[/latex] [latex]\left|\sqrt{x}-y_{i} \right|[/latex] i Комментарий
5 1e-2 2.236069 9.18e-07 4 Пройден
100 1e-1 10.000053 5.29e-05 6 Пройден
100 1e-2 10.000000 1.40e-10 7 Пройден
100 1e-6 10.000000 0.00e+00 8 Пройден
100 1e-10 10.000000 0.00e+00 9 Пройден

Решение.

C++

Java

Для подсчета значения квадратного корня для заданного числа создадим цикл. Цикл выполняется пока [latex]\left|y_{i}-y_{i-1}>=\varepsilon\right|[/latex].

С повышением точности растёт количество итераций, но из-за того что, начиная с [latex]\varepsilon=10^{-5}[/latex], погрешность не вычисляется, зависимость оценить нельзя.

Для выполнения программы и проверки тестов можно воспользоваться следующей ссылкой(C++) или другой(Java).

А137в

Задача.

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

Тесты.

n [latex]a_{1}…a_{n}[/latex] [latex]\left|a_{1} \right|, \left|a_{1}+a_{2} \right|, … , \left|a_{1}+…+a_{n} \right|[/latex] Комментарий
5 -5  6  11  -10 5  1  12  2 Пройден
4 -4.2  5.6  0  -3.2 4.2  1.4  1.4  1.8 Пройден

Код.

C++

Java

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

Для выполнения программы и проверки тестов можно воспользоваться следующей ссылкой(C++) или другой(Java).

А116в

Задача.

Даны натуральное число [latex]n[/latex], действительное число [latex]x[/latex]. Вычислить: [latex]\sum_{i=1}^{n}{\frac{x+cos(ix)}{2^{i}}}[/latex]

Тесты. 

n x sum Комментарий
5 2 1.65 Пройден
10 10 9.67 Пройден
5 0 0.97 Пройден

Все тесты проверены на wolframalpha.

Код.

C++

Java

 

Для решения данной задачи воспользуемся циклом for, также для упрощения вычислений (не считать [latex]2^{i}[/latex] каждый раз заново) введем переменную degree.

Для выполнения программы и проверки тестов можно воспользоваться следующей ссылкой(C++) или другой(Java).

А59к

Задача.

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

A59k

Тесты.

Ввод Вывод
[latex](-5.25;1.5)[/latex] Принадлежит
[latex](-3;1)[/latex] Принадлежит
[latex](0.6;0.6)[/latex] Принадлежит
[latex](-0.8;0.9)[/latex] Принадлежит
[latex](0.5;0.4)[/latex] Не принадлежит
[latex](-0.25;-0.3)[/latex] Не принадлежит

Код.

(C++)

Java

Решение.

Решение задачи сводится к поиску условия, при котором точка будет принадлежать данной части плоскости. В данной задаче условие будет такое: точка находиться выше прямой [latex]y=1[/latex], то есть ордината точки [latex]y\geq 1[/latex] (границы включаем) или точка находится выше графика функции [latex]y=\left|x \right|[/latex] на промежутке [latex]x[/latex]∈ [latex]\left[-1;1 \right][/latex], то есть [latex]y\geq \left|x \right|[/latex] , [latex]-1\leq x\leq 1[/latex] (границы включаем).

Для выполнения программы и проверки тестов можно воспользоваться следующей ссылкой(C++)  или другой(Java).

Ю2.17

Задача.

Как известно число делится на 3, тогда и только тогда, когда сумма его цифр делится на 3. Проверить этот признак на примере заданного трехзначного числа.

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

Тесты.

Ввод Вывод Комментарий
321 not refuted В обоих случаях кратно 3.
742 not refuted В обоих случаях не кратно 3.

Код.

C++

Java

 Алгоритм.

  1. Проверяем кратно ли данное число 3-ем.
  2. Находим сумму цифр числа.
  3. Проверяем кратна ли сумма цифр 3-ем.
  4. Сравниваем результаты.

Для выполнения программы и проверки тестов можно воспользоваться следующей ссылкой(C++) или другой(Java).

Ю1.22

Задача.

Треугольник задается координатами своих вершин на плоскости: [latex]A(x1,y1)[/latex], [latex]B(x2,y2)[/latex], [latex]C(x3,y3)[/latex]. Найти площадь треугольника ABC.

Тесты.

A B C Площадь Комментарий
[latex](0;0)[/latex] [latex](0;4)[/latex] [latex](5;0)[/latex] 10 Пройден
[latex](-1.5;2)[/latex] [latex](2.5;-2)[/latex] [latex](4;4.25)[/latex] 15.5 Пройден
[latex](0;1)[/latex] [latex](0;3)[/latex] [latex](0;4)[/latex] 0 Пройден

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

Код.

С++

Java

Решение.

Для вычисления площади воспользуемся формулой:

[latex]S_{ABC}=\frac{\left|(x_{B}-x_{A})(y_{C}-y_{A})-(x_{C}-x_{A}) (y_{B}-y_{A})\right|}{2}[/latex]

Для выполнения программы и проверки тестов можно воспользоваться данной ссылкой (C++) или другой (Java).