Una striscia di terra
I residenti di Dingilville stanno cercando di localizzare una regione
per costruire un aeroporto. Avete a disposizione la mappa del suolo disponibile.
La mappa è una griglia rettangolare di quadrati unitari ciascuno definito
da una coppia di coordinate (x,y), dove x è la coordinata
orizzontale (ovest-est) e y quella
verticale (sud-nord). L'altezza
di ogni quadrato è mostrata sulla mappa.
Il vostro
compito è di trovare una regione rettangolare di quadrati con l'area
più grande (cioè una regione rettangolare costituita dal massimo
numero di quadrati possibile) tale che:
- la
differenza di altezza tra i quadrati più alti e quelli più bassi della
regione sia inferiore o uguale al limite C dato, e
- la larghezza (cioè il numero di quadrati lungo la direzione
ovest-est) della regione sia al massimo 100.
Nel caso
ci siano più regioni di questo tipo è richiesto di rilevarne solo una.
Assunzioni
-
1 <= U <=700, 1 <= V <=700, dove U e V
designano le dimensioni della mappa. In modo più specifico, U
è il numero di quadrati nella direzione ovest - est, e V, nella
direzione sud - nord.
- 0
<= C <= 10
- -30,000
<= Hxy <= 30,000,
dove l'intero Hxy è l'altezza del quadrato alle coordinate
(x,y), 1 <= x <= U, 1 <= y <= V.
- il quadrato
dell'angolo sud ovest della mappa ha coordinate (1,1) e quello dell'angolo
nord est ha coordinate (U,V)
Dati in input
- L'input
è un file di testo chiamato land.inp.
-
La prima
riga contiene tre interi: U, V e C.
- Ciascuna
delle seguenti V righe contiene gli interi Hxy
per x=1,...,U. Più specificatamente, Hxy
è l'x-esimo numero sulla (V-y+2)-esima riga
di input.
Dati in output
L'output deve essere un file di testo di nome land.out
con una riga contenente 4 interi
che localizzano la regione trovata: Xmin,
Ymin, Xmax, Ymax,
dove (Xmin , Ymin ) sono le coordinate
del quadrato dell'angolo sud ovest e (Xmax, Ymax)
le coordinate del quadrato dell'angolo nord-est della regione.
Esempio di input e output
Valutazione
Al programma è concesso un tempo di esecuzione di al massimo
130 secondi.
Non sono previsti punteggi parziali.