Matrius amb marc nul P77360


Statement
 

pdf   zip

Donada una matriu MM de mida m×nm\times n, i una posició (i,j)(i,j) dins d’ella, diem que el marc de MM és la suma dels elements a l’esquerra i al damunt de la posició (i,j)(i,j) (amb la fila ii i la columna jj incloses). Altrament dit, el marc de (i,j)(i,j) és ∑p=1i∑q=1jMp,q\sum_{p=1}^i\sum_{q=1}^j M_{p,q}. Un marc és nul si val zero.

Per exemple, per la matriu

(32−45761−3−448−43−2−1−2−163−7−2−30−2−38−4566)\left( \begin{array}{rrrrrr} 3 & 2 & -4 & 5 & 7 & 6 \\ 1 &-3 & -4 & 4 & 8 & -4 \\ 3 &-2 & -1 &-2 &-1 & 6 \\ 3 &-7 & -2 &-3 & 0 & -2 \\ -3 & 8 & -4 & 5 & 6 & 6 \\ \end{array} \right)

el marc de (2,4)(2,4) és 3+2−4+5+1−3−4+4=43+2-4+5+1-3-4+4 = 4 i el marc de (4,2)(4,2) és 3+2+1−3+3−2+3−7=03+2+1-3+3-2+3-7 = 0. Per tant, el marc de (4,2)(4,2) és nul.

Feu un programa que, donada una matriu, indiqui si aquesta té algun marc nul.

Entrada

L’entrada és una matriu d’m×nm\times n enters. Primer es donen dos enters mm i nn (amb m,n≥1m,n\ge 1) i després els mnmn enters.

Sortida

La sortida ha d’indicar si la matriu té algun marc nul o no, seguint el format dels exemples.

Observació

El vostre algorisme ha de funcionar en temps lineal respecte el nombre d’elements a la matriu.

Public test cases

  • Input

    5 6
        3   2  -4   5   7   6 
        1  -3  -4   4   8  -4 
        3  -2  -1  -2  -1   6 
        3  -7  -2  -3   0  -2 
       -3   8  -4   5   6   6

    Output

    True

  • Input

    5 6
        3   2  -4   5   7   6 
        1  -3  -4   4   8  -4 
        3  -2  -1  -2  -1   6 
        3  -6  -2  -3   0  -2 
       -3   8  -4   4   6   6

    Output

    False
    • Information
    Author
    Jordi Petit
    Language
    Catalan
    Official solutions
    Python
    User solutions
    Python