Obeleži sve kategorije koje odgovaraju problemu

Petar ima ogroman voćnjak šljiva koji je idealno organizovao tako da su šljive poređane u $N$ redova (vrsta) i $N$ kolona. Visine svih stabala su pozitivni celi brojevi. Ne postoje dva stabla iste visine. Pri tome je stabla tako oblikovao tako da za svaku vrstu važi da visine stabala sleva nadesno obrazuju rastući ili opadajući niz (mogu postojati vrste poređane u rastućem, ali isto tako i vrste poređane u opadajućem poretku, na potpuno slučajan način poređane). Slično za svaku kolonu važi da visine stabala od prvog prema poslednjem obrazuju rastući ili opadajući niz (mogu postojati kolone u kojima su poređane u rastućem poretku i kolone u kojima su poređane u opadajućem poretku, ali poredak vama nije poznat). Vrste su numerisane brojevima od $1$ do $N$, a kolone brojevima od $1$ do $N$. Na raspolaganju imate funkciju (kasnije će biti detaljno opisana) kojom možete dobiti visinu stabla koje se nalazi u određenoj vrsti i koloni (zvaćemo tu funkciju upit). Potrebno je da sa što manje upita odredite da li u voćnjaku postoji stablo zadate visine i poziciju tog stabla, ako postoji (redni broj vrste i redni broj kolone). Zato će biti zadat prirodan broj $K$. Ako vaš program u ne više od $K$ upita odgovori tačno smatra se da je vaš program korektno rešio taj test primer, u suprotnom, smatra se da je rešenje primera netačno.

Opisi funkcija

Potrebno je da implementirate funkciju

• $Resi(N, K, V, I, J)$

koja treba da odredi da li se u voćnjaku sa $N$ vrsta i $N$ kolona nalazi stablo visine $V$ i ako se nalazi odredi redni broj vrste i redni broj kolone u kome se nalazi stablo visine $V$. Ako stablo ne postoji, onda vrednosti za redni broj vrste i redni broj kolone treba da budu 0. $K$ je predviđeni broj upita.

Na raspolaganju imate funkciju

• $DajVisinu(I, J)$

koja treba da vrati visinu stabla koje se nalazi u vrsti $I$ i kooni $J$. Ako koordinate $I$ i $J$ nisu u dozvoljenim granicama, funkcija vraća vrednost $-1$.

Primer

Neka je $N = 4, K = 16, V = 9$, a matrica sa visinama stabala:

3 6 10 15
5 9 13 18
31 27 23 20
45 28 32 25

Ako je prvi upit bio za polje $(2, 4)$ odgovor bi bio $18$. Ako je drugi upit za polje $(2,1)$ odgovor bi bio $5$. Konačno, ako je treći upit za polje $(2,2)$ odgovor bi bio 9, pa bi vaša funkcija mogla da vrati rešenje $I=2$, $J=2$.

Ograničenja

• $N \leq 1000$
• $K \leq 10000$
• Visine stabala si između $1$ i $100.000.000$

Podzadaci

• Podzadatak 1 [8 poena]: $N \leq 100$, $K = N \times N$.
• Podzadatak 2 [14 poena]: $N \leq 1.000$, $K = 10.000$.
• Podzadatak 3 [24 poena]: $N \leq 1.000$, $K = 6.000$.
• Podzadatak 4 [54 poena]: $N \leq 1.000$, $K = 4.000$.

Detalji implementacije

Potrebno je da pošaljete tačno jedan fajl vocnjak.cpp ili vocnjak.pas, koji implementira pomenutu funkciju. Osim tražene funkcije, vaš fajl može sadržati i dodatne globalne promenljive, pomoćne funkcije i dodatne biblioteke.

U zavisnosti od programskog jezika koji koristite, vaša funkcija/procedura mora biti sledećeg oblika:

| Jezik | Deklaracija funkcije |