Fişierul intrare/ieşire:struti.in, struti.outSursăpreONI 2006 Runda 2
AutorFilip Cristian BuruianaAdăugată de
Timp execuţie pe test1.25 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Struti

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 km2 cuprinse in teren. Pentru ca strutii sa se dezvolte optim, diferenta de altitudine a terenului ales trebuie sa fie cat mai mica posibil.

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.

Cerinta

Determinati diferenta de altitudine mimima pentru fiecare oferta in parte.

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.

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.

Restrictii si precizari

  • 3 ≤ M, N ≤ 1 000
  • P ≤ 10
  • 1 < DX, DY ≤ 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

Exemplu

struti.instruti.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

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 95 4 8 9  5 4 8 9
3 8 5 8  3 8 5 83 8 5 8  3 8 5 8
2 0 6 4  2 0 6 4  2 0 6 4  2 0 6 4|

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content