Dana jest trójwymiarowa tablica
Znaleźć lokalne maksimum, czyli komórkę, w której wartość jest nie mniejsza niż wartości w 6 sąsiadach tej komórki.
Tablica ma rozmiar
Zakładamy, że pozycja szukanej komórki jest w przedziale
Następnie pytamy się o liczby z dwóch środkowych komórek przedziału,
czyli dla
Z kolei gdy
Dla podzadania 1 mamy
int n1,n2,n3,q; map<tuple<int,int,int>,int> memo; int ask(int x, int y, int z) { if (x <= 0 || x > n1 || y <= 0 || y > n2 || z <= 0 || z > n3) return 0; auto key = make_tuple(x, y, z); if (memo.find(key) != memo.end()) { return memo[key]; } printf("? %d %d %d\n", x, y, z); fflush(stdout); int h; scanf("%d",&h); return memo[key] = h; } void answer(int x, int y, int z) { printf("! %d %d %d\n", x, y, z); exit(0); } int ask(int x) { return ask(x, 1, 1); } int answer(int x) { answer(x, 1, 1); } int main() { scanf("%d%d%d%d",&n1,&n2,&n3,&q); assert(n2 == 1 && n3 == 1); int x1=1, x2=n1; while (x2 != x1) { int mid = (x2+x1) / 2; int hl = ask(mid), hr = ask(mid+1); if (hl >= hr) { x2 = mid; } else { x1 = mid+1; } } answer(x1); }
Dla podzadania 2 potrzebujemy zadać nie więcej niż 35 pytań. Użyjemy tutaj techniki znanej jako metoda złotego podziału.
W przedziale
Dla uproszczenia rozważań niech oryginalny przedział ma długość 1 i chcemy dobrać długość
1-s 2s-1 1-s |---------|-----|---------| x1 xL xR x2
Chcemy, żeby punkt
Zatem zadamy teraz około
Ponieważ powyższe obliczenia zakładają, że możemy zadawać pytania w dowolnych punktach rzeczywistych, to przy implementacji warto zapamiętać pytania, które zadaliśmy i zaokrąglać wyniki do tej liczby całkowitej, dla której zadaliśmy już pytanie. Ponadto, pod koniec algorytmu, dla krótkiego przedziału, bezpiecznie przełączyć się na zwykłe wyszukiwanie binarne:
bool inmemo(int x) { auto key = make_tuple(x, 1, 1); return memo.find(key) != memo.end(); } int adjust(int x) { if (inmemo(x)) return x; else if (inmemo(x-1)) return x-1; else if (inmemo(x+1)) return x+1; else return x; } int main() { scanf("%d%d%d%d",&n1,&n2,&n3,&q); assert(n2 == 1 && n3 == 1); int x1=1, x2=n1; while (x2-x1 > 20) { const double s = (sqrt(5)-1)/2.; int pl = adjust(s*x1 + (1-s)*x2); int pr = adjust((1-s)*x1 + s*x2); int hl = ask(pl), hr = ask(pr); if (hl >= hr) { x2 = pr-1; } else { x1 = pl+1; } } while (x2 != x1) { int mid = (x2+x1) / 2; int hl = ask(mid), hr = ask(mid+1); if (hl >= hr) { x2 = mid; } else { x1 = mid+1; } } answer(x1); }
Spróbujemy ugólnić wyszukiwanie binarne na tablicę kwadratową
Ponadto, będziemy utrzymywać pozycję pewnej komórki
Na początku oczywiście
Będziemy dzielić prostokąt na połowy, na zmianę prostymi poziomymi i pionowymi.
Dla podziału poziomego sprawdzamy wartości na wszystkich komórkach
na linii
Jeśli
W przeciwnym wypadku lewy i dolny sąsiad komórki
A jeśli pierwsza z nich ma wartość większą, czyli
Kod może wyglądać następująco:
int main() { scanf("%d%d%d%d",&n1,&n2,&n3,&q); assert(n3 == 1); int x1=1, x2=n1, y1=1, y2=n2; bool horiz = 1; int xo, yo, ho=-1; while (x2 != x1 || y2 != y1) { int xm, ym, hm=-1; if (horiz) { int ymid = (y1+y2)/2; for (int x=x1; x<=x2; ++x) { int h = ask(x, ymid); if (h > hm) { hm = h; xm = x; } } if (ho > hm) { assert(yo != ymid); if (yo < ymid) { y2 = ymid-1; } else { y1 = ymid+1; } } else { if (int ha = ask(xm, ymid-1); ha > hm) { y2 = ymid-1; xo = xm; yo = ymid-1; ho = ha; } else if (int ha = ask(xm, ymid+1); ha > hm) { y1 = ymid+1; xo = xm; yo = ymid+1; ho = ha; } else { answer(xm, ymid); } } } else { // vert int xmid = (x1+x2)/2; for (int y=y1; y<=y2; ++y) { int h = ask(xmid, y); if (h > hm) { hm = h; ym = y; } } if (ho > hm) { assert(xo != xmid); if (xo < xmid) { x2 = xmid-1; } else { x1 = xmid+1; } } else { if (int ha = ask(xmid-1, ym); ha > hm) { x2 = xmid-1; xo = xmid-1; yo = ym; ho = ha; } else if (int ha = ask(xmid+1, ym); ha > hm) { x1 = xmid+1; xo = xmid+1; yo = ym; ho = ha; } else { answer(xmid, ym); } } } horiz ^= 1; } answer(x1, y1); }
Zatem startujemy z prostokąta o wymiarach
Tak więc liczba zadanych przez nas pytań wyraża się rekurencją
Tutaj już skorzystamy z tego, że program sprawdzający nie jest adaptatywny, zatem możemy spróbować jakiegoś rozwiązania randomizowanego.
Taki bardzo prosty program mógłby sprawdzić
W pesymistycznym przypadku te pomysły się nie sprawdzą, ale ich połączenie radzi sobie
całkiem nieźle.
A konkretnie: najpierw sprawdzamy
Jakie jest zatem prawdopodobieństwo, że żadna z
const int MX[] = {-1,1,0,0,0,0}, MY[] = {0,0,-1,1,0,0}, MZ[] = {0,0,0,0,-1,1}; int main() { scanf("%d%d%d%d",&n1,&n2,&n3,&q); int mx,my,mz, mh=-1; REP(i,q/2) { int x = rand()%n1 + 1, y = rand()%n2 + 1, z = rand()%n3 + 1; int h = ask(x, y, z); if (h > mh) { mx = x; my = y; mz = z; mh = h; } } REP(i,q/2) { int ok = 1; REP(mo,6) { int nx = mx + MX[mo], ny = my + MY[mo], nz = mz + MZ[mo]; int h = ask(nx, ny, nz); if (h > mh) { mx = nx; my = ny; mz = nz; mh = h; ok = 0; break; } } if (ok) { answer(mx, my, mz); } } }