Matrius de Monge P16242

Una matriu n × m es diu que és una matriu de Monge (en honor al matemàtic francès Gaspard Monge) si, per a tots els i, j, k, ℓ tals que 0 ≤ i < k < n i 0 ≤ j < ℓ < m, es compleix

Per exemple, aquesta matriu és de Monge:

Si prenem la intersecció de les files 1 i 3 amb les columnes 0 i 4, els quatre elements són:

Fixem-nos que 17 + 7 ≤ 11 + 23. Aquesta propietat es compleix a tot arreu de la matriu.

Feu una funció

tal que, donada una matriu M de mides n × m, amb n ≥ 2 i m ≥ 2, retorni cert si i només si M és de Monge.

Observació Només cal enviar el procediment demanat; el programa principal serà ignorat.

Observació

El jutge acceptarà solucions amb cost Θ(n² · m²), però no són eficients i això es penalitzarà a la correcció manual.