Question

Вам дана матрица размера N×M, состоящая из целых положительных чисел, а также целое число K. Назовем подматрицу хорошей, если она является квадратом и сумма этой подматрицы не больше K. Посчитайте количество хороших подматриц. Подматрицей называется такая матрица, которую можно получить из исходной, если удалить из нее несколько(возможно ноль) столбцов с левого и правого края, а также несколько(возможно ноль) строк с верхнего и нижнего края. При этом подматрица не должна быть пустой. Входные данные В первой строке заданы 3 целых числа N, M, K — размеры матрицы. (1≤N,M≤1500, 0≤K≤109) В следующих N строках содержится по M целых положительных чисел — содержимое матрицы (числа по значению от 1 до 1000). Выходные данные Выведите одно число — количество подходящих подматриц. Система оценки Данная задача содержит 6 подзадач, в которых выполняются следующие ограничения: Тесты из условия. Оценивается в 0 баллов. N,M≤2. Оценивается в 15 баллов. N,M≤100. Оценивается в 17 баллов. N,M≤500. Оценивается в 24 балла. N,M≤1500 и матрица состоит только из единичек. Оценивается в 15 баллов. Исходные ограничения. Оценивается в 29 баллов. Примеры входные данныеСкопировать 3 3 12 1 2 3 5 2 5 3 2 4 выходные данныеСкопировать 12 входные данныеСкопировать 6 6 30 4 4 4 1 1 1 2 5 5 3 2 3 3 2 2 4 1 3 1 1 4 4 4 5 1 3 3 4 5 5 2 5 5 4 3 4 выходные данныеСкопировать 71

Answer 1

Ответ:

ты тоже на олипе сидиш?

Объяснение:

Answer 2

У меня не выводит сложение всех чисел, как найти?

Язык: Python

from random import random

M = int(input())

N = int(input())

a = []

for i in range(N):

   b = []

   for j in range(M):

       b.append(int(random()*11))

       print("%3d" % b[j], end='')

   a.append(b)

   print('   |', sum(b))

 

for i in range(M):

   print(" --", end='')

print()

 

for i in range(M):

   s = 0

   for j in range(N):

       s += a[j][i]

   print("%3d" % s, end='')

print()

Answer 3

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

1. Создайте массив префиксной суммы размером NxM, где каждый элемент представляет сумму всех элементов в соответствующем подматрице. Это можно сделать, пройдя по матрице слева направо, сверху вниз, и на каждом шаге добавляя текущий элемент к предыдущему.

2. Создайте двумерный массив dp размером NxM, где dp[i][j] будет хранить количество хороших подматриц, которые заканчиваются на элемент (i, j).

3. Заполните массив dp, пройдя по матрице справа налево, снизу вверх. Для каждого элемента (i, j), проверьте все возможные квадратные подматрицы, которые заканчиваются на этом элементе. Если сумма этих подматриц не превышает K, увеличьте dp[i][j] на 1 и добавьте это значение к dp[i-1][j-1], если это возможно.

4. В конце, сумма всех элементов в массиве dp будет равна количеству хороших подматриц.

Вот пример кода на Python, который реализует этот алгоритм:

def count_good_submatrices(n, m, k, matrix):
   prefix_sum = [[0]*(m+1) for _ in range(n+1)]
   for i in range(1, n+1):
       for j in range(1, m+1):
           prefix_sum[i][j] = prefix_sum[i-1][j] + prefix_sum[i][j-1] - prefix_sum[i-1][j-1] + matrix[i-1][j-1]

dp = [[0]*m for _ in range(n)]
   for i in range(n-1, -1, -1):
       for j in range(m-1, -1, -1):
           for x in range(i, n):
               for y in range(j, m):
                  if prefix_sum[x][y] - prefix_sum[i-1][y] - prefix_sum[x][j-1] + prefix_sum[i-1][j-1] <= k:
                      dp[i][j] += 1
                      if i > 0 and j > 0:
                          dp[i][j] += dp[i-1][j-1]

return sum(sum(row) for row in dp)

Обратите внимание, что этот код предполагает, что индексация матрицы начинается с 0, а не с 1. Если индексация начинается с 1, как указано в условии задачи, вам нужно будет немного изменить код.