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).