Omówienie zadania Skarb (III etap XXXI OI)

Pierwsze podejście - rozwiązanie losowe

Zadawanie pytań o losowe względnie pierwsze liczby z przedziału $[1, n]$ pozwala zdobyć trochę punktów. Może mieć ono pewne problemy, gdy $x$ jest mały (a $n$ duże), ponieważ może ciągle dostawać odpowiedzi typu "$\texttt{/"$", które nie będą dawać dużo informacji. Aby sobie z tym poradzić warto wzbogacić to rozwiązanie o zadawanie pytań o małe liczby naturalne.

Żeby znaleźć rozwiązania pasujące do zadanych zapytań, w przypadku małych $n$ wystarczające jest trzymanie liczby wszystkich liczb spełniających dotychczasowe warunki. Aby poradzić sobie z większymi liczbami, przydatne jest Chińskie Twierdzenie o Resztach . Warto również zawuażyć, że odpowiedzi typu "$\texttt{/}$" tak na prawdę nakładają ograniczenia dolne i górne na wynik.

Przy dobrej implementacji takie rozwiązanie pozwala zdobyć około 25 punktów.

Rozwiązanie pierwiastkujące:

W tym rozwiązaniu będziemy starać się odtworzyć zapis binarny liczby $x$. Zauważmy, że jeżeli zapytamy o $2^k$, to:

w przypadku odpowiedzi $\texttt{%}$ dowiemy się jakie jest $k$ ostatnich bitów $x$
w przypadku odpowiedzi $\texttt{/}$ dowiemy się jakie jest $64-k$ pierwszych bitów $x$

Wybierając odpowiednio parametr $k$, program z każdym zapytaniem będzie poznawał połowę bitów odpowiedzi, których jeszcze nie zna. Dokładniej, jeżeli zna $a$ początkowych oraz $b$ końcowych bitów wyniku, a nie zna środkowych $c = 64 - a - b$, to zapyta o $2^{b + c/2}$. Wtedy, zgodnie z poprzednią obserwacją, niezależnie od odpowiedzi poznamy dodatkowe $c/2$ bitów.

Po 6 takich zapytaniach zostanie nam jeden bit, którego nie znamy, czyli dwie możliwe odpowiedzi. Możemy wtedy zapytać o większą z nich, dostając jednoznaczną odpowiedź. Daje to rozwiązanie z pesymistyczną ilością 7 zapytań na ostatnim podzadaniu.

Takie rozwiązanie pozwala zdobyć 74 punkty.

Rozwiązanie wzorcowe:

Aby przekształcić rozwiązanie pierwiastkujące, skorzystamy z następującej obserwacji:

Jeżeli aktualnie zbiór możliwych odpowiedzi tworzy $A$ kolejnych liczb dających tę samą restę z dzielenia przez $B$, gdzie $A < B$, to każda z tych możliwości ma inną część całkowitą oraz inną resztę z dzielenia przez $B-1$. Zatem w takim wypadku wystarczy nam jedno zapytanie o tę liczbę.

Jeżeli będziemy korzystać z powyższej obserwacji, to pytanie o $2^{b+c/2}$ może już nie być optymalne. Zamiast tego możemy rozważyć zapytanie o $2^{b+d}$ dla dowolnego $d \in [1, c-1]$. Aby dowiedzieć się, jak dokładnie zadawać pytania, możemy użyć programowania dynamicznego. Niech $\texttt{dp[a][b]}$ oznacza minimalną liczbę ruchów potrzebną do wygranej znając $a$ pierwszych oraz $b$ ostatnich bitów wyniku. Wtedy \[ \texttt{dp[a][b]} = \begin{cases} 1 & \text{jeżeli $64 - a - b < b$ lub $a + b >= 63$} \\ 1 + \min_d(\max(\texttt{dp[a][b+d]}, \texttt{dp[64-b-d][b]})) & \text{w przeciwnym przypadku} \end{cases} \]

Empirycznie sprawdzając ile wynosi $\texttt{dp[0][0]}$, dowiadujemy się, że zadanie da się rozwiązać w czterech pytaniach. Zawartość tablicy $\texttt{dp}$ pozwala dowiedzieć się jakie konkretne pytania zadać.

Rozwiązanie alternatywne - drzewo decyzyjne

Kluczem w tym rozwiązaniu jest obserwacja, że jeżeli znamy część całkowitą z dzielenia przez 4, to możemy wygrać w 2 ruchy (napierw pytając o 2, a następnie o większą z możliwości które zostaną).

Rozważmy następujące drzewo decyzyjne zapytań.

                         div A    +-------+    mod A
               +------------------|   A   |------------------+
               |                  +-------+                  |
     div 4 +-------+ mod 4                         div E +-------+ mod E
   +-------|   4   |-------+                     +-------|   E   |-------+
   |       +-------+       |                     |       +-------+       |
wygrana                    |                     |                       |
+2 kroki                   |                     |                       |
                 div B +-------+ mod B       +-------+               +-------+
               +-------|   B   |-------+     |   F   |               |   G   |
               |       +-------+       |     +-------+               +-------+
               |                       |
           +-------+               +-------+
           |   C   |               |   D   |
           +-------+               +-------+

Liczby $A, \ldots, G$ to jeszcze nieznane stałe. Zaraz dobierzemy je tak, by zachować następującą własność:

Jeżeli dostaliśmy wcześniej odpowiedź $\texttt{%}$ na zapytanie o liczbę $M$, to później będziemy zadawać pytania jedynie o liczby względnie pierwsze z $M$.

Teraz będziemy zadawać pytania, schodząc po drzewku decyzyjnym. Będziemy pamiętać: resztę z dzielenia $x$ przez $P$, gdzie $P$ jest iloczynem liczb ze wszystkich zapytań, dla których dostaliśmy odpowiedź $\texttt{%}$; i wartość $\lfloor x/Q \rfloor$ dla najmniejszego $Q$, dla którego dostaliśmy tę odpowiedź. Zauważmy, że jeśli $P \geq Q$, to możemy odzyskać $x$ bez zadawania dalszych pytań.

Spróbujmy odtworzyć, jakie powinny być kolejne stałe:

Zacznijmy od $C$. Chcemy, żeby:
- $C$ było jak największe,
- $C < B < A$,
- by dało się odzyskać poprawne $x$ po wszystkich zapytaniach.
W tej ścieżce znamy resztę z dzielenia $x$ przez $4$ oraz znamy część całkowitą z dzielenia $x$ przez $C$, więc $C \leq 4$. Ale też $C$ musi być względnie pierwsze z $4$, więc po prostu $C = 3$.
W przypadku $B$, spójrzmy na ścieżkę kończącą się w $C$. Znamy resztę z dzielenia $x$ przez $12$ oraz część całkowitą z dzielenia $x$ przez $B$, więc zgodnie z zasadami ($B \leq 12$ oraz B względnie pierwsze z 12) weźmy na przykład $B = 11$.
Dla $D$ znamy resztę z dzielenia $x$ przez $44$ oraz część całkowitą z dzielenia $x$ przez $D$, wieć wybierzmy $D = 43$.
Znając całe lewe poddrzewo, możemy dobrać $A$. Będąc w wierzchołku $D$ znamy resztę z dzielenia $x$ przez 1892 oraz część całkowitą dzielenia $x$ przez $A$, więc wybierzmy $A = 1891$.
Przyjrzyjmy się prawemu poddrzewu, zakładając że $F < E$. Jak dostaniemy odpowiedź dzielenia w $F$, to będziemy znać resztę z dzielenia $x$ przez $1891$ oraz część całkowitą z dzielenia $x$ przez $F$, więc weźmy $F = 1890$.
W takim razie jak dostaniemy odpowiedź modulo przez $F$, to będziemy znać resztę z dzielenia $x$ przez $3573990$ oraz część całkowitą dzielenia $x$ przez $E$, więc wybierzemy $E = 3573989$.
Jak rozważymy część całkowitą z dzielenia przez $G$, to do tej pory będziemy znać resztę z dzielenia $x$ przez $6758413199$. Zatem możemy wziąć $G=6758413198$.
Z kolei w przypadku reszty z dzielenia przez $G$, znamy w sumie resztę z dzielenia $x$ przez $45676148961659000402 > 2^{64}$, więc rzeczywiście wygraliśmy.

Teraz wystarczy zadać odpowiednie pytania i wywnioskować odpowiedź.