Concursul 'IBM Linux Scholar'



Se consideră o matrice A de dimensiune M x N ale cărei elemente au valoarea 0. Se aleg K cvadrupli de numere x1, y1, x2, y2 cu 1 <= x1 <= x2 <= N și 1 <= y1 <= y2 <= M. Pentru fiecare astfel de cvadruplu valoarea tuturor elementelor Aij (x1 <= j <= x2, y1 <= i <= y2) crește cu 1.
    Dându-se o matrice A, să se determine un număr cât mai mic de cvadrupli care să ducă la obținerea matricei A, pornind de la o matrice care are toate elementele nule.

Fișierul de intrare MATRIX.IN conține numărul de linii M și numărul de coloane N ale matricei, separate printr-un singur spațiu. Fiecare dintre următoarele M linii va conține N numere naturale, separate prin spații; al j-lea număr de pe a i-a dintre aceste N linii reprezintă valoarea elementului Aij.

Prima linie a fișierului de ieșire MATRIX.OUT va conține numărul K al cvadruplilor folosite. Fiecare dintre următoarele K linii va conține cele patru numere din componența unui cvadruplu, în ordinea x1, y1, x2, y2, separate prin spații.

1 <= M, N <= 100;
0 <= Aij <= 255.

MATRIX.IN
5 6
1 2 2 1 1 0
1 3 3 2 2 0
1 3 3 2 2 0
0 2 2 3 3 1
0 1 1 2 2 1

MATRIX.OUT
4
2 2 5 4
1 1 3 3
2 1 5 5
4 4 6 5

Numerele scrise cu roșu în fișierul de ieșire au fost modificate conform precizărilor din anunțul general.

Vom considera că pentru fiecare test, se vor putea obține cel mult X puncte.     Concurenții care vor găsi cea mai mică valoare Kmin prin care se poate obține matricea A, vor primi X puncte pentru testul respectiv.
    Ceilalți concurenți, care au reușit să obțină matricea A folosind K > Kmin cvadrupli, vor obține X * Kmin / K puncte pentru testul respectiv. Această valoare va fi aproximată cu două zecimale exacte.
    Punctajul final va fi obținut prin adunarea punctajelor de la fiecare test și rotunjirea acestuia la cel mai apropiat număr întreg.
    Dacă cvadruplii din fișierul de ieșire nu duc la obținerea matricei A sau programul nu respectă limita de timp admisă, concurenții nu vor primi nici un punct pentru testul respectiv.
    De exemplu, dacă pentru un test se pot obține cel mult 5 puncte, cel mai bun rezultat obținut de un concurent constă în 7 cvadrupli, iar un alt concurent obține o soluție cu 12 cvadrupli, atunci, pentru testul respectiv, punctajul concurentului va fi de 5 * 7 / 12 = 2.92 puncte.