[naglowek]

wersja PS     wersja PS.ZIP
Wstęp
Sprawozdanie z przebiegu VII OI
Regulamin
Zasady organizacji zawodów
Informacja o IOI'99
Etap I
Etap II
Etap III
IOI
 
Kwiaciarnia
Kody
Podziemne miasto
Światła drogowe
Spłaszczanie
Pas ziemi
Literatura

Spis treści
O wersji online

Niebieskie książeczki
 
Olimpiada Informatyczna
Kącik zadań
Archiwum zadań
CEOI'97
 
   Krzysztof Diks, Marcin Kubica (przekład)

Pas ziemi

Mieszkańcy Dingiville próbują znaleźć lokalizację dla lotniska. Mają przed sobą mapę. Mapa jest prostokątną siatką jednostkowych kwadratów. Każdy kwadrat jest identyfikowany przez parę współrzędnych (x,y), gdzie x jest współrzędną poziomą (zachód-wschód), a y jest współrzędną pionową (południe-północ). Dla każdego kwadratu podana jest jego wysokość.

Twoim zadaniem jest znaleźć prostokątny obszar (zbudowany z jednostkowych kwadratów) o największej powierzchni (tj. liczbie zawartych w nim kwadratów) oraz taki, że:

  1. różnica wysokości między najwyższym i najniższym kwadratem obszaru nie przekracza podanego ograniczenia C, oraz
  2. szerokość obszaru (tzn. liczba kwadratów w kierunku zachód-wschód) wynosi co najwyżej 100.

W przypadku gdy jest wiele takich obszarów należy podać jeden z nich.

Założenia

  • 1 le U le 700, 1 le V le 700, gdzie U i V są wymiarami mapy. Dokładniej, U jest liczbą kwadratów w kierunku zachód-wschód, a V liczbą kwadratów w kierunku południe-północ.
  • 0 le C le 10
  • -30,000 le H_xy  le 30,000, gdzie liczba całkowita Hxy jest wysokością kwadratu o współrzędnych (x,y), 1 le x le U, 1 le y le V.
  • Południowo-zachodni róg mapy ma współrzędne (1,1), a róg północno-wschodni ma współrzędne (U,V).

Wejście

Plikiem wejściowym jest plik tekstowy o nazwie land.inp.

  • Pierwszy wiersz zawiera trzy liczby całkowite: U, V i C.
  • Każdy z kolejnych V wierszy zawiera liczby całkowite Hxy, dla x=1,...,U. Dokładniej, Hxy jest x-tą liczbą w (V-y+2)-gim wierszu.

Wyjście

Wynikiem jest plik tekstowy land.out złożony z jednego wiersza zawierającego cztery liczby całkowite: Xmin, Ymin, Xmax, Ymax. Opisują one znaleziony obszar - (X_min , Y_min) są współrzędnymi jego południowo-zachodniego rogu, a (X_max , Y_max) są współrzędnymi jego północno-wschodniego rogu.

Przykład

land.inp:

10 15 4
41 40 41 38 39 39 40 42 40 40
39 40 43 40 36 37 35 39 42 42
44 41 39 40 38 40 41 38 35 37
38 38 33 39 36 37 32 36 38 40
39 40 39 39 39 40 40 41 43 41
39 40 41 38 39 38 39 39 39 42
36 39 39 39 39 40 39 41 40 41
31 37 36 41 41 40 39 41 40 40
40 40 40 42 41 40 39 39 39 39
42 40 44 40 38 40 39 39 37 41
41 41 40 39 39 40 41 40 39 40
47 45 49 43 43 41 41 40 39 42
42 41 41 39 40 39 42 40 42 42
41 44 49 43 46 41 42 41 42 42
45 40 42 42 46 42 44 40 42 41

 limgland1.1Rys. 1. PrzykŞa...

land.out:

4 5 8 11

Ocena

Ograniczenie czasowe na czas działania Twojego programu wynosi 60 sekund. Nie można otrzymać części punktów za pojedynczy test.