Drevni programer Cep Lu Splus provodi dane mrzeći žalbe i mrzeći provođenje dana u mržnji. Povremeno mu dolaze sećanja na drevna vremena kada je bio član Komisije i odbijao žalbe najbolje od svih. Jednom, u ta vremena, dobio je izuzetno neosnovanu žalbu i dok je hodao drevnom planinom u potrazi za znakom da li da je prvo pročita ili prvo odbije -- žalba mu je ispala iz ranca i bi zauvek izgubljena. Od tada ga ovo mrsko sećanje neprestano progoni i zbog toga ne može da spava.
Ali sada ste došli vi, zaštitnici takmičara koji se žale, i odlučili da pronađete planinu na kojoj je izgubljena žalba. Poznato je da je Cep tog sudbonosnog dana bio u oblasti koja liči na kvadratnu matricu dimenzija čije svako polje predstavlja neku planinu određene visine. Kako Cep mrzi niske planine i kolone, planina na kojoj je on bio tog dana je strogo viša od svih ostalih planina iz svoje vrste. Analogno, kako Cep mrzi slanu plazmu i radne subote, ta planina je ujedno i strogo niža od svih ostalih planina iz svoje kolone.
Loša vest je što vi ne znate visine planina a još gora što Cep zna. No, njegova mržnja prema mrskim sećanjima i nesanici je blago jača od mržnje prema vama i on će vam iskreno odgovarati na pitanja oblika "kolika je visina planine koja se nalazi u -toj vrsti i -toj koloni?". Jasno, Cep mrzi drevni broj i ne želite da znate šta će se desiti ukoliko mu postavite više od pitanja.
Pronađite bar jednu planinu na kojoj je mogla biti izgubljena žalba ili konstatujte da takva planina ne postoji postavljajući ne više od pitanja. Neka izgubljena žalba konačno bude i formalno odbijena...
Opisi funkcija
Potrebno je da implementirate funkciju
koja treba da odredi da li se u matrici planina sa vrsta i kolona nalazi planina koja je strogo veća od svih ostalih planina iz svoje vrste i strogo manja od svih ostalih planina iz svoje kolone. Ova funkcija mora da vrati niz (vektor) dužine 2 koji sadrži, redom, brojeve i koji označavaju da je tražena planina u preseku -te vrste i -te kolone. Vrste i kolone su indeksirane od 1. Ukoliko ima više rešenja, vratiti bilo koje; ukoliko nema rešenja vratiti niz sa dve nule.
Na raspolaganju imate funkciju
koju smete pozvati najviše puta. Ova funkcija vraća visinu planine u preseku -te vrste i -te kolone. Ukoliko su koordinate i van opsega, funkcija će vratiti .
Primer
Neka je , i neka su visine planina u matrici:
3 9 9
2 2 7
7 5 8
Za npr. upit , odgovor bi bio ; za upit odgovor bi bio ; za upit odgovor bi bio itd. Jedino rešenje za ovaj primer je planina u preseku druge vrste i treće kolone (visina 7) i vaša funkcija mora da vrati niz koristeći ne više od upita.
Ograničenja
- Visine svih planina su prirodni brojevi iz segmenta .
Podzadaci
- Podzadatak 1 [4 poena]: ,
- Podzadatak 2 [9 poena]: ,
- Podzadatak 3 [12 poena]: , , visine planina su , ili
- Podzadatak 4 [18 poena]: ,
- Podzadatak 5 [19 poena]: ,
- Podzadatak 6 [14 poena]: ,
- Podzadatak 7 [24 poena]: ,
Detalji implementacije
Potrebno je da pošaljete tačno jedan fajl planine.cpp
koji implementira pomenutu funkciju. Osim tražene funkcije, vaš fajl može sadržati i dodatne globalne promenljive, pomoćne funkcije i dodatne biblioteke.
Vaša funkcija mora biti sledećeg oblika:
std::vector<int> Nadji(int N, int K);
Vaša funkcija može koristiti funkciju
int Pitaj(int i, int j);
Da bi funkcija Pitaj
bila "vidljiva" vašoj funkciji Nadji
, potrebno je dodati liniju #include "code.h"
na početku fajla koji sadrži implementaciju funkcije Nadji
.
Testiranje i eksperimentisanje
Uz zadatak, obezbeđen vam je "template" fajl code.cpp
koji možete koristiti i menjati po potrebi. Takođe vam je obezbeđeni program grader.cpp
koji služi da lakše testirate kodove. Ovaj program učitava sa standardnog ulaza sledeće podatke:
- U prvom redu brojeve i
- U narednih redova po brojeva koji predstavljaju visine planina
a zatim poziva vašu funkciju sa učitanim parametrima i . Na kraju, na standardni izlaz štampa, redom, brojeve , i , gde su i redni broj vrste i kolone koje je vratila vaša funkcija a broj poziva funkciji Pitaj
. Kodove ovih programa možete menjati po potrebi. Ne garantuje se da će za testiranje biti korišćena baš ova verzija programa grader.cpp
.
Comments