Kolory

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ń.

Mało kolorów

W podzadaniu 1 mamy $N\le 64$, zatem możemy zapytać o wszystkie możliwe wartości $C$, czyli kolejno o różnice $N-1,N-2,N-3,\dots ,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,\dots$$

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\le 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,\dots$ W przypadku odpowiedzi negatywnej, zadajemy $N/2$ pytań o różnice $N-1,N-2,\dots$

Średnia liczba kolorów

W podzadaniu 3 mamy $N\le 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,\dots$

Dużo kolorów

Jeśli chcemy znaleźć rozwiązanie dla $N\le {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);
}