e-olymp 683. Частичная сумма матрицы

Задача

Задана матрица чисел $a_{ij}$ где $1 \leqslant i \leqslant n$, $1 \leqslant j \leqslant m$. Для всех $i, j$ найдите $$S_{i,j}=\sum_{k=1, t=1}^{k\leqslant i, t \leqslant j}a_{kt}.$$

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

В первой строке записаны размеры матрицы — $n, m$ $(1 \leqslant n, m \leqslant 1000)$. В последующих $n$ строках записано по $m$ чисел $a_{ij}$ $(1 \leqslant a_{ij} \leqslant 1000)$.

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

Выведите $n$ строк по $m$ чисел $S_{i,j}$.

Тесты

Входные данные Выходные данные
3 5
1 2 3 4 5
5 4 3 2 1
2 3 1 5 4
1 3 6 10 15
6 12 18 24 30
8 17 24 35 45
4 4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 2 3 4
2 4 6 8
3 6 9 12
4 8 12 16
6 7
15 78 69 36 567 654 5
54 54 52 81 237 5 98
987 2 65 5 32 89 67
541 89 4 32 4 1 40
68 7 345 6 21 23 56
9 5 7 2 5 4 1000
15 93 162 198 765 1419 1424
69 201 322 439 1243 1902 2005
1056 1190 1376 1498 2334 3082 3252
1597 1820 2010 2164 3004 3753 3963
1665 1895 2430 2590 3451 4223 4489
1674 1909 2451 2613 3479 4255 5521

Код программы

 

Решение

Создаем  матрицу x[1001][1001]  вне int main() . Сдвигаем индексацию массива на единицу и заполняем его. Таким образом первая строка и первый столбец у нас оказываются заполнены нулями. Чтобы не вычислять каждую новую $S_{i,j}$ от $(i+1)\cdot (j+1)$ предыдущих значений, воспользуемся основным свойством частичных сумм: если $$S_{i,j}=\sum_{k=1, t=1}^{k\leqslant i, t \leqslant j}a_{kt},$$ то тогда $S_{i,j} — a_{ij}=S_{i-1,j}+S_{i,j-1}-S_{i-1,j}\cap S_{i,j-1}$, где $S_{i-1,j}\cap S_{i,j-1} = S_{i-1,j-1}$. Тогда при $1 \leqslant i \leqslant n$, $1 \leqslant j \leqslant m$ вычисляем частичные суммы по формуле: $$S_{i,j} = S_{i-1,j}+S_{i,j-1}-S_{i-1,j-1}+a_{ij}.$$

Ссылки

Условие задачи на E-olymp

Код программы на IdeOne

e-olymp 8524. Сумма положительных в матрице

Задача взята с сайта e-olymp

Условие

Задана матрица размера [latex]n\times n[/latex]. Найдите сумму ее положительных элементов.

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

Первая строка содержит число [latex]n[/latex] [latex]\left(1 \leq n \leq 100 \right)[/latex]. Следующие строки содержат матрицу [latex]n\times n[/latex]. Элементы матрицы по модулю не больше [latex]100[/latex].

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

Выведите сумму положительных элементов матрицы.

Тесты

Inputs Outputs
1 3
4 -2 5
1 -4 -12
0 1 -3
11
2 4
-4 -2 -5 -7
-1-14 -4 -12
-12 -1 -3 -53
0
3 3
0 0 0
0 1 0
0 0 0
1
4 0 0
5 5
89 76 54 32 33
46 57 89 40 32
12 45 63 78 65
13 76 54 89 67
13 67 89 90 43
1412

Код

Решение

В условии сказано, что задана матрица размера [latex]n\times n[/latex], тогда вводов тоже будет, соответственно, [latex]n\cdot n[/latex]. В цикле ввода используется условный оператор для проверки на то, положительно число или нет.

Ссылки

Ю3.23

Текущее среднее. Числа [latex]x_{1},x_{2},..[/latex] последовательно поступают с устройства ввода. Все числа хранить в памяти нет необходимости; после ввода каждого числа нужно вычислить и напечатать среднее значение всех введенных чисел: [latex]S_{n}=\frac{1}{n}\sum_{k=1}^{n}x_{k}[/latex].

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

Создаем цикл, в котором «n» раз будем считывать «x» и суммировать при помощи переменной «s», а затем делить на «текущее» количество переменных в цикле при помощи счетчика цикла.

Тесты:

[latex]n=4[/latex]

[latex]x[/latex] Числа: Результат:
[latex]x_{1}[/latex] 1 1, 4, 5.33333, 46.
[latex]x_{2}[/latex] 7
[latex]x_{3}[/latex] 8
[latex]x_{4}[/latex] 168

[latex]n=6[/latex] 

[latex]x[/latex] Числа: Результат:
[latex]x_{1}[/latex] 9.5 9.5, 6.7, 4.40042, 506.8, 399.418, 342.849.
[latex]x_{2}[/latex] 3.9
[latex]x_{3}[/latex] -0.19873
[latex]x_{4}[/latex] 2014
[latex]x_{5}[/latex] -30.11
[latex]x_{6}[/latex] 60

 

 

Ссылка на код.