Aceasta problema, cea de-a 38-a, va fi ultima problema propusa pe lista anul
acesta. Deadline-ul ei este de abia pe 11 ianuarie, adica la inceputul
scolii. Problema este deosebit de interesanta si in plus extrem de dificila.
Ea este propusa de colegul meu de facultate, Alex Susu, care a propus mai
multe probleme frumoase pe lista, caruia ii multumesc inca o data pentru acest
lucru si caruia - si in numele vostru - il rog sa mai propuna in continuare
astfel de probleme.
Deci,
----------------------------------------
| PROBLEMA 38: The Matrix has you! ;) |
| PUNCTAJ: 100 Dexteri |
| DEADLINE: Marti, 11 Ianuarie 2000 |
| TIMP DE IMPLEMENTARE: 110 minute |
| TIMP DE EXECUTIE: 4 sec./test (266Mhz) |
----------------------------------------
Data o matrice binara de dimensiuni MxN (3<=M,N<=700) se cere sa se
determine aria dreptunghiului de intindere maxima care contine doar 1.
Matricea se citeste din fisierul text MATRIX.IN care va avea urmatoarea
structura:
- pe prima linie cele doua numere naturale M si N
- urmatoarele M linii vor avea cate N cifre de 0 sau 1 despartite
printr-un spatiu.
Ceea ce se cere este sa se scrie pe singura linie a fisierului text
MATRIX.OUT numarul natural care reprezinta aria determinata.
Exemplu:
MATRIX.IN
8 9
1 1 0 1 1 1 0 1 1
0 0 1 0 1 1 0 0 0
1 0 0 1 1 0 1 0 1
0 0 1 0 1 1 1 1 0
1 0 0 1 1 0 1 1 0
1 1 1 1 0 1 1 1 1
0 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1
MATRIX.OUT
12
Observatie:
Cele 4 secunde de rulare le-am impartit astfel: 2 secunde pentru citire
date de intrare + 2 secunde rezolvare propriu-zisa problema.
Se garanteaza ca se vor da si teste cu valori ale lui M si N mai mici de
200.
Complexitate recomandata: O(M*N).
|
|