Linda lubi zmieniać kolor włosów (kolory numerujemy liczbami od 1 do $N$) i wie, że jej chłopak to zauważy, jeśli różnica bezwzględna między starym a nowym kolorem wynosi co najmniej $C$.
Linda chce wyznaczyć wartość $C$, wykonując zmiany kolorów włosów i obserwując reakcje chłopaka. Nie można dwa razy użyć tego samego koloru. Należy napisać program, który pozwoli jej to zrobić, używając jedynie 64 zapytań.
W podzadaniu 1 mamy $N \leq 64$, zatem możemy zapytać o wszystkie możliwe wartości $C$, czyli kolejno o różnice $N-1, N-2, N-3, \ldots, 1$. Gdy dla którejś z różnicy $c$ odpowiedź chłopaka będzie negatywna, tzn. że mamy $C=c+1$. W przeciwnym wypadku mamy $C=1$.
Kłopotliwe jest jedynie wybieranie kolorów tak, aby żaden z nich się nie powtórzył. Wystarczy jednak użyć kolorów w następującej kolejności: $$1, N, 2, N-1, 3, N-2, \ldots$$
W celu uproszczenia implementacji, będziemy zapamiętywać ostatnio zadane pytanie $prev$. Jeśli nowe pytanie jest o pozycję $p$, to powiemy, że robimy skok $p-prev$. Ponieważ kolejne skoki na liście mają naprzemienne znaki, więc również możemy zapamiętać znak ostatniego skoku. Funkcja jump pobiera jedynie długość skoku:
ll n, previous, dir; int ask(ll p) { printf("? %lld\n",p); fflush(stdout); int resp; scanf("%d",&resp); return resp; } void answer(int ans) { printf("= %lld\n", ans); exit(0); } int jump(ll jump) { ll pos = previous + dir*jump; previous = pos; dir *= -1; return ask(pos); } int main() { scanf("%lld",&n); dir = 1; previous = 1; ask(previous); REP(i,n-1) { if (!jump(n-1-i)) { answer(n-i); } } answer(1); }
W drugim podzadaniu mamy $N \leq 125$. Jeśli więc $N>64$, to możemy najpierw zadać pytanie o różnicę $m = \lceil N/2 \rceil - 1$. W przypadku odpowiedzi pozytywnej, uruchamiamy poprzedni algorytm zadający $N/2$ pytań o różnice $m-1,m-2,\ldots$ W przypadku odpowiedzi negatywnej, zadajemy $N/2$ pytań o różnice $N-1,N-2,\ldots$
W podzadaniu 3 mamy $N \leq 1000$, co może być sugestią, że można zadać jedynie „piewiastkową” liczbę pytań.
Podzielimy nasze rozwiązanie na dwie fazy: najpierw oszacujemy wartość $C$ z dokładnością do $\sqrt{N}$, zadając $\sqrt{N}$ pytań. Dzięki temu, będziemy wiedzieć, że $C$ należy do przedziału od $l = k\sqrt{N}$ do $r = (k+1) \sqrt{N}$. W drugiej fazie, za pomocą dodatkowych $\sqrt{N}$ pytań o różnice $r-1,r-2,\ldots$
Jeśli chcemy znaleźć rozwiązanie dla $N \leq 10^{18}$, to musi ono zadać $\log N + O(1)$ pytań. Naturalnym więc pomysłem jest wyszukiwanie binarne. Musimy jednak uważać, aby nie powtórzyć żadnego koloru.
Po pierwsze, tak jak w pierwszym rozwiązaniu, zrobimy założenie, że skoki mają naprzemienne znaki i że zaczynamy skokiem w prawo. Po drugie, podejdziemy do zadania rekurencyjnie. Chcemy znaleźć strategię dla $N$ kolorów, czyli przedziału $[1,N]$.
Załóżmy na początek, że $N = 2M$ jest parzyste. Niech $f_M$ będzie pierwszym pytaniem, które zadajemy w strategii dla $M$ kolorów:
fM fN fN+M |---+--------| => |--------+---|--------+---|
Strategię dla $N$ kolorów zaczniemy od pytania $f_N$, po którym zrobimy skok w prawo o długości $M$ (czyli do pytania $f_N+M$).
Jeśli odpowiedź na pytanie była pozytywna, to znaczy, że ograniczyliśmy się do przedziału $[1,M]$, przy czym następny skok musimy wykonać w lewo. Zatem chcielibyśmy przełączyć się teraz na strategię dla $M$ kolorów, ale wykonywać skoki w drugą stronę. Taka strategia wymaga pierwszego pytania w punkcie $M+1-f_M$. Musimy więc zadbać o to, żeby pytanie $f_N$, które zadaliśmy w przedziale $[1,M]$ było kompatybilne z tą strategią, czyli $f_N = M+1-f_M$.
Jeśli odpowiedź na pytanie była negatywna, to ogranicza nas to do przedziału $[M+1,2M]$. Okazuje się, że tutaj też możemy zastosować strategię dla $M$ kolorów, ale każdy skok musimy zwiększyć o $M$. Zauważmy, że przy takich skokach żaden kolor w przedziale $[1,N]$ się nie powtórzy, bo będziemy skakać na przemian pomiędzy lewą a prawą połową przedziału, a pozycje pytań wzięte modulo $M$ będą odpowiadały dokładnie pozycjom ze strategii dla $M$ kolorów (jest też tak dla początkowej pozycji $f_N+M$).
Tak więc po dokładnie jednym skoku zmniejszyliśmy długość przedziału dwukrotnie.
Przypadek gdy $N = 2M-1$ jest nieparzyste bazuje na tym samym pomyśle, ale jest ciut bardziej wymagający technicznie. Teraz dwa kawałki długości $M$ będą w przedziale długości $N$ nachodzić na siebie jednym polem:
fM fN fN+M-1 |---+--------| => |--------+--|--|-------+---|
Pierwsze pytanie zadamy w $f_N = M+1-f_M$, ale pierwszy skok będzie miał długość $M-1$.
Jeśli odpowiedź na pytanie była pozytywna, to ograniczyliśmy się do przedziału $[1,M-1]$. Tutaj zastosujemy strategię (z rozpoczynającym skokiem w drugą stronę) dla $M-1$ kolorów. Kluczowa jest obserwacja, że $f_{M-1}$ jest równe $f_M$ lub $f_M-1$, zatem przedział pozycji, w którym będziemy wykonywali skoki, zmieści się w lewej części długości $M$.
Jeśli odpowiedź była negatywna, to ograniczamy się do przedziału $[M,2M-1]$, więc zastosujemy tutaj strategię dla $M$ kolorów, przy czym każdy skok zwiększymy o $M-1$. Tu z kolei kluczowe jest, że wszystkie skoki będą dłuższe niż $M$, zatem nigdy nie wykonamy skoku na środkowe pole.
W implementacji tego rozwiązania możemy połączyć oba przypadki w jeden. Funkcja first oblicza pozycję pierwszego pytania, a funkcja run implementuje strategię (jej drugi parametr określa o jak dużo mamy zwiększać wszystkie skoki):
ll first(ll n) {
if (n == 1) { return 1; }
ll m = (n+1) / 2;
return m + 1 - first(m);
}
ll run(ll n, ll incr) {
if (n == 1) { return 1; }
ll m = (n+1) / 2, ms = n-m;
if (jump(ms + incr)) {
return run(ms, incr);
} else {
return ms + run(m, incr + ms);
}
}
int main() {
scanf("%lld",&n);
dir = 1;
previous = first(n);
ask(previous);
ll ans = run(n, 0);
answer(ans);
}