Idi na tekst

5 - Voćnjak

Vremensko ograničenje Memorijsko ograničenje
1000ms 128MB

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 1

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
C++ void Resi(int N, int K, int V, int *I, int *J);
Pascal procedure Resi(N, K, V: longint; var I, J: longint);

U zavisnosti od programskog jezika koji koristite, vaša funkcija/procedura može koristiti fuknciju:

Jezik Deklaracija funkcije
C++ int DajVisinu(int I, int J);
Pascal function DajVisinu(I, J: longint): longint;

Testiranje i eksperimentisanje

Uz zadatak, obezbeđeni su vam "template" fajlovi code.cpp i code.pas koje možete koristiti i menjati po potrebi. Takođe su vam obezbeđeni programi grader.cpp, grader.pas koji služe da lakše testirate kodove. Ovi programi učitavaju sa standardnog ulaza sledeće podatke:

  • U prvom redu brojeve \(N, K, V\),
  • U narednih \(N\) redova po \(N\) brojeva, brojevi koji predstavljaju visine stabala po redovima u voćnjaku.

Zatim ovaj program zove vašu funkciju i štampa brojeve \(I\), \(J\) i \(T\). \(I, J\) su redni broj vrste i kolone koje je vratila vaša funkcija, a \(T\) je broj poziva funkcije \(DajVisinu\). Kodove ovih programa možete menjati po potrebi, ali će za testiranje biti korišćena originalna verzija ovih programa.

Autor Tekst i test primeri Analiza rеšenja Testiranje
Nikola Milosavljević Dragan Urošević Bhuvnesh Jain Nikola Spasić

Možete pročitati editorijal na engleskom (CodeChef je koristio naš zadatak za Challenge rundu): Link

05_vocnjak.cpp
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
# include <stdio.h>
# include "code.h"

# define MAXN 1010
int smv[MAXN], smk[MAXN];
int npv, npk;
int a[MAXN][MAXN];



void Nadji(int i1, int j1, int i2, int j2, int vv, int *ii, int *jj) {
    int i, j;
    if (smv[i1] == 1) {
        if (smk[j2] == 1) {
            i = i1; j = j2;
            while (i <= i2) {
//              printf("cc %d %d\n", i, j);
                if (a[i][j] == 0)
                    a[i][j] = DajVisinu(i, j);
                if (a[i][j] == vv) {
                    *ii = i; *jj = j; return;
                }
                if (vv < a[i][j]) {
                    j--;
                    if (j < j1) return; // j < j1
                } else {
                    if (j < j2) j++;
                    if (++i > i2) return;
                }
            }                       
        } else {
            i = i2; j = j2;
            while (i >= i1) {
//              printf("cc %d %d\n", i, j);
                if (a[i][j] == 0)
                    a[i][j] = DajVisinu(i, j);
                if (a[i][j] == vv) {
                    *ii = i; *jj = j; return;
                }
                if (vv < a[i][j]) {
                    j--;    
                    if (j < j1) return; // j < j1
                } else {
                    if (j < j2) j++;
                    if (--i < i1) return;
                }
            }                       
        }
    } else {
        if (smk[j2] == 1) {
            i = i1; j = j1;
            while (i <= i2) {
//              printf("cc %d %d\n", i, j);
                if (a[i][j] == 0)
                if (a[i][j] == 0)
                    a[i][j] = DajVisinu(i, j);
                if (a[i][j] == vv) {
                    *ii = i; *jj = j; return;
                }
                if (vv < a[i][j]) {
                    j++; 
                    if (j > j2) return;
                } else {
                    if (j > j1) j--;
                    if (++i > i2) return;
                }
            }                       
        } else {
            i = i2; j = j1;
            while (i >= i1) {
//              printf("cc %d %d\n", i, j);
                if (a[i][j] == 0)
                    a[i][j] = DajVisinu(i, j);
                if (a[i][j] == vv) {
                    *ii = i; *jj = j; return;
                }
                if (vv < a[i][j]) {
                    j++;
                    if (j > j2) return; 
                } else {
                    if (j > j1) j--;
                    if (--i < 1) return;
                }
            }                       
        }
    }
}





void Resi2x2AA(int n, int i1, int j1, int vv, int *ii, int *jj) {
    int i, j;
    int radi[2][2] = {{1,1},{1,1}};
//  printf("Ovde %d %d %d %d\n", i1, j1, a[i1-1][j1-1], a[i1][j1]);
    if (vv > a[i1-1][j1-1]) {
        radi[0][0] = 0;
    } else {
        radi[0][1] = radi[1][0] = 0;
    }
    if (vv > a[i1][j1]) {
        radi[1][1] = 0;
    } else {
        radi[0][1] = radi[1][0] = 0;
    }
//  printf("%d\n", radi[0][1]);
    if (radi[0][0]) {
        Nadji(1, 1, i1-1, j1-1, vv, ii, jj);
        if ((*ii != 0) && (*jj != 0)) return;
    }
    if (radi[0][1]) {
        Nadji(1, j1, i1-1, n, vv, ii, jj);
        if ((*ii != 0) && (*jj != 0)) return;
    }
    if (radi[1][0]) {
        Nadji(i1, 1, n, j1-1, vv, ii, jj);
        if ((*ii != 0) && (*jj != 0)) return;
    }
    if (radi[1][1]) {
        Nadji(i1, j1, n, n, vv, ii, jj);
        if ((*ii != 0) && (*jj != 0)) return;
    }   
}


void Resi2x2BB(int n, int i1, int j1, int vv, int *ii, int *jj) {
    int i, j;
    int radi[2][2] = {{1,1},{1,1}};
//  printf("Ovde %d %d %d %d\n", i1, j1, a[i1-1][j1-1], a[i1][j1]);
    if (vv < a[i1-1][j1-1]) {
        radi[0][0] = 0;
    } else {
        radi[0][1] = radi[1][0] = 0;
    }
    if (vv < a[i1][j1]) {
        radi[1][1] = 0;
    } else {
        radi[0][1] = radi[1][0] = 0;
    }
//  printf("%d\n", radi[0][1]);
    if (radi[0][0]) {
        Nadji(1, 1, i1-1, j1-1, vv, ii, jj);
        if ((*ii != 0) && (*jj != 0)) return;
    }
    if (radi[0][1]) {
        Nadji(1, j1, i1-1, n, vv, ii, jj);
        if ((*ii != 0) && (*jj != 0)) return;
    }
    if (radi[1][0]) {
        Nadji(i1, 1, n, j1-1, vv, ii, jj);
        if ((*ii != 0) && (*jj != 0)) return;
    }
    if (radi[1][1]) {
        Nadji(i1, j1, n, n, vv, ii, jj);
        if ((*ii != 0) && (*jj != 0)) return;
    }   
}




void Resi2x2(int n, int vv, int *ii, int *jj) {
    int i, j, i1, j1, i2, j2;
    i1 = 1; j1 = 1;
    *ii = *jj = 0;
    while (smv[i1] == smv[1]) i1++;
    while (smk[j1] == smk[1]) j1++;
    a[i1-1][j1-1] = DajVisinu(i1-1, j1-1);  
    a[i1-1][j1] = DajVisinu(i1-1, j1);  
    a[i1][j1-1] = DajVisinu(i1, j1-1);  
    a[i1][j1] = DajVisinu(i1, j1);  
    if (a[i1-1][j1-1] == vv) {
        *ii = i1-1; *jj = j1-1; return; 
    }
    if (a[i1-1][j1] == vv) {
        *ii = i1-1; *jj = j1; return; 
    }
    if (a[i1][j1-1] == vv) {
        *ii = i1; *jj = j1-1; return; 
    }
    if (a[i1][j1] == vv) {
        *ii = i1; *jj = j1; return; 
    }
    if ((smv[1] == 1) && (smk[1] == 1)) {
        Resi2x2AA(n, i1, j1, vv, ii, jj);
        return; 
    }
    if ((smv[1] == -1) && (smk[1] == -1)) {
        Resi2x2BB(n, i1, j1, vv, ii, jj);
        return; 
    }

}


void ResiV(int n, int vv, int *ii, int *jj) {

    int nadjen = 0;
    int i, j, i1, i2;
    i2 = 1;
    *ii = *jj = 0;
    while (i2 <= n) {
        i1 = i2;
        while ((i2 <= n) && (smv[i2] == smv[i1])) i2++;
//      printf("AA %d %d %d\n", i1, i2, vv);
        if (smk[1] == 1) {
            if (smv[i1] == -1) {
                a[i2-1][1] = DajVisinu(i2-1, 1);
                if (vv <= a[i2-1][1]) {
                    nadjen = 1; break;
                }
            } else {
                a[i2-1][n] = DajVisinu(i2-1, n);
                if (vv <= a[i2-1][n]) {
                    nadjen = 1; break;
                }
            }
        } else {
            if (smv[i1] == -1) {
                a[i2-1][n] = DajVisinu(i2-1, n);
                if (vv >= a[i2-1][n]) {
                    nadjen = 1; break;
                }
            } else {
                a[i2-1][1] = DajVisinu(i2-1, 1);
                if (vv >= a[i2-1][1]) {
                    nadjen = 1; break;
                }
            }
        }
    }
//  printf("BB %d %d\n", i2, a[i2-1][n]);
    if (!nadjen) {
        *ii = *jj = 0;
        return;
    }
    i2--;
    Nadji(i1, 1, i2, n, vv, ii, jj);


}

void ResiK(int n, int vv, int *ii, int *jj) {
    int nadjen = 0;
    int i, j, j1, j2;
    j2 = 1;
    *ii = *jj = 0;
    while (j2 <= n) {
        j1 = j2;
        while ((j2 <= n) && (smk[j2] == smk[j1])) j2++;
//      printf("AA %d %d %d\n", j1, j2, vv);
        if (smv[1] == 1) {
            if (smk[j1] == -1) {
                a[1][j2-1] = DajVisinu(1, j2-1);
                if (vv <= a[1][j2-1]) {
                    nadjen = 1; break;
                }
            } else {
                a[n][j2-1] = DajVisinu(n, j2-1);
                if (vv <= a[n][j2-1]) {
                    nadjen = 1; break;
                }
            }
        } else {
            if (smk[j1] == -1) {
                a[n][j2-1] = DajVisinu(n, j2-1);
                if (vv >= a[n][j2-1]) {
                    nadjen = 1; break;
                }
            } else {
                a[1][j2-1] = DajVisinu(1, j2-1);
                if (vv >= a[1][j2-1]) {
                    nadjen = 1; break;
                }
            }
        }
    }
//  printf("BB %d %d\n", j2, a[n][j2-1]);
    if (!nadjen) {
        *ii = *jj = 0;
        return;
    }
    j2--;
    Nadji(1, j1, n, j2, vv, ii, jj);
}


void Resi(int n, int k, int vv, int *ii, int *jj) {
    int i, j;
    a[1][1] = DajVisinu(1, 1);
    a[1][2] = DajVisinu(1, 2);
    if (a[1][1] < a[1][2]) smv[1] = 1; else smv[1] = -1;
    for (i = 2; i < n; i++) {
        a[i][i] = DajVisinu(i, i);
        a[i][i+1] = DajVisinu(i, i+1);
        if (a[i][i] < a[i][i+1]) smv[i] = 1; else smv[i] = -1;
        if (a[i-1][i] < a[i][i]) smk[i] = 1; else smk[i] = -1;
    }
    a[n][n] = DajVisinu(n, n);
    a[n][1] = DajVisinu(n, 1);
    if (a[n][1] < a[n][n])  smv[n] = 1; else smv[n] = -1;
    if (a[1][1] < a[n][1])  smk[1] = 1; else smk[1] = -1;
    if (a[n-1][n] < a[n][n]) smk[n] = 1; else smk[n] = -1;
    npv = npk = 1;
    for (i = 2; i <= n; i++) {
        if (smv[i-1] != smv[i]) npv++;
        if (smk[i-1] != smk[i]) npk++;
    }   

//  printf("%d %d\n", npv, npk);

    if (npv == 1) {
        ResiK(n, vv, ii, jj);
        return;
    }
    if (npk == 1) {
        ResiV(n, vv, ii, jj);
        return;
    }
    Resi2x2(n, vv, ii, jj);
}