struti

Struti

== include(page="template/taskheader" task_id="struti") ==

==Include(page="template/taskheader" task_id="struti")==

Poveste ...

Patratel s-a lasat de scoala si, pentru ca a aflat ca sunt foarte profitabile, s-a apucat de afaceri cu struti. Pentru a demara afacerea sa, el are nevoie mai intai de toate sa cumpere teren in regiune. Regiunea este dreptunghiulara si are dimensiunile de $M$ km x $N$ km, fiind impartita in zone de $1$ x $1$ km. Fiecare zona are o altitudine cunoscuta, specificata pe harta in metri fata de nivelul marii. Astfel, toate altitudinile sunt numere intregi nenegative. Terenul pe care Patratel vrea sa il cumpere in aceasta regiune trebuie sa fie de asemenea dreptunghiular si sa aiba laturile paralele cu ale regiunii. In plus, terenul nu trebuie ales la intamplare. Pentru ca a studiat comportamentul strutilor, el si-a dat seama ca sunt animale destul de pretentioase. Se defineste diferenta de altitudine a unui teren ca fiind diferenta dintre altitudinea maxima si altitudinea minima ale unor zone de $1$ km^2^ cuprinse in teren. Pentru ca strutii sa se dezvolte optim, diferenta de altitudine a terenului ales trebuie sa fie cat mai mica posibil.

h2. Cerinta
 
...

Patratel primeste $P$ oferte pe care trebuie sa le analizeze. O oferta este formata dintr-o pereche de numere naturale ({$DX DY$}), semnificand faptul ca Patratel poate alege oriunde in regiune un teren cu laturile de dimensiuni $DX$ si $DY$ ( nu neaparat in aceasta ordine ). Pentru fiecare oferta in parte Patratel ar dori sa stie care este diferenta de altitudine minima a unui teren cu laturile specificate in oferta.

h2. Restrictii

h2. Cerinta

...

Determinati diferenta de altitudine mimima pentru fiecare oferta in parte.

h2. Date de intrare

...

Prima linie a fisierului $struti.in$ contine $M$, $N$ si $P$, dimensiunile regiunii si numarul de oferte, despartite de cate un spatiu. Pe fiecare din urmatoarele $M$ linii se afla cate $N$ numere naturale nenegative, specificand altitudinea zonei respective. Urmatoarele $P$ linii descriu cate o oferta, compusa din doua numere naturale $DX$ si $DY$, cu semnificatiile descrise in enunt.

h2. Date de iesire

...

Fisierul $struti.out$ contine $P$ linii, pe linia $i$ aflandu-se $MIN$ si $NR$, diferenta de altitudine minima pentru oferta a $i$-a si numarul de terenuri posibile cu aceasta diferenta minima.
 
h2. Restrictii si precizari
 
* $3 ≤ M, N ≤ 1 000$
* $P ≤ 10$
* $1 < DX, DY &le; minim(M, N)$
* Fiecare teren selectat trebuie sa fie inclus complet in regiune
* Toate altitudinile sunt date in metri si nu depasesc $8 000$
* Punctele pe un test se acorda doar daca fisierul de iesire este in intregime corect

h2. Exemplu

| struti.in | struti.out |
| linia1
linia2
linia3
| linia1
linia2

table(example). |_. struti.in|_. struti.out|
|4 4 2
1 4 3 2
5 4 8 9
3 8 5 8
2 0 6 4
2 3
2 2
|5 4
4 4

|

== include(page="template/taskfooter" task_id="struti") ==

h3. Explicatii
 
Cele patru terenuri care pot fi selectate pentru prima oferta sunt cele ingrosate:
{$1 4 3 2   1 4 3 2   1 4 3 2   1 **4 3** 2$}
{$5 4 **8 9**   5 **4 8 9**   **5 4 8** 9   5 **4 8** 9$}
{$3 8 **5 8**   3 **8 5 8**   **3 8 5** 8   3 **8 5** 8$}
{$2 0 **6 4**   2 0 6 4   2 0 6 4   2 0 6 4|$}
 
==Include(page="template/taskfooter" task_id="struti")==
 
 

733