package example

object Matrix extends App {
  type Matrix = Array[Array[Int]]

  def printMatrix(m: Matrix) =
    for (l <- m) println(l.mkString(", "))

  def solve(N: Matrix, m: Int): (Matrix, Matrix) = {
    val n = N.length

    var M: Matrix = Array.ofDim[Int](m, m)
    var MN: Matrix = Array.ofDim[Int](m, n)

    val k = n - m

    for (r <- 0 until n) {
      val mn_r = if (r > k) r - k else 0

      for (c <- 0 until n) {
        // заполняем MN
        if (mn_r == 0) // первый ряд просто накапливает сумму
          MN(mn_r)(c) = MN(0)(c) + N(r)(c)
        else // следующие ряды берут сумму из ячейки выше, и обновляют её
          MN(mn_r)(c) = MN(mn_r - 1)(c) + N(r)(c) - N(mn_r - 1)(c)

        if (r >= k) {
          // заполняем M
          val m_c = if (c > k) c - k else 0
          if (m_c == 0)
            M(mn_r)(m_c) = M(mn_r)(0) + MN(mn_r)(c)
          else
            M(mn_r)(m_c) = M(mn_r)(m_c - 1) + MN(mn_r)(c) - MN(mn_r)(m_c - 1)
        }
      }
    }

    (MN, M)
  }

  def go(m: Matrix, k: Int) = {
    printMatrix(m)
    println()
    val t = solve(m, k)
    printMatrix(t._1)
    println()
    printMatrix(t._2)
  }

  val m1: Matrix =
    Array(
      Array(1, 1, 1, 1, 1),
      Array(2, 2, 2, 2, 2),
      Array(3, 3, 3, 3, 3),
      Array(4, 4, 4, 4, 4),
      Array(5, 5, 5, 5, 5))

  val m2 = Array(
    Array(1, 2, 3),
    Array(4, 5, 6),
    Array(7, 8, 9))

  go(m1, 3)
  go(m2, 2)

}