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 "$\mathtt{\text{/}}$" 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 $\mathtt{\text{\%}}$ dowiemy się jakie jest $k$ ostatnich bitów $x$
• w przypadku odpowiedzi $\mathtt{\text{/}}$ 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 $\mathtt{\text{dp[a][b]}}$ oznacza minimalną liczbę ruchów potrzebną do wygranej znając $a$ pierwszych oraz $b$ ostatnich bitów wyniku. Wtedy $$\mathtt{\text{dp[a][b]}}=\{\begin{array}{ll}1& \text{jeżeli }64-a-b<b\text{ lub }a+b>=63\\ 1+\underset{d}{min}(max(\mathtt{\text{dp[a][b+d]}},\mathtt{\text{dp[64-b-d][b]}}))& \text{w przeciwnym przypadku}\end{array}$$

Empirycznie sprawdzając ile wynosi $\mathtt{\text{dp[0][0]}}$, dowiadujemy się, że zadanie da się rozwiązać w czterech pytaniach. Zawartość tablicy $\mathtt{\text{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,\dots ,G$ to jeszcze nieznane stałe. Zaraz dobierzemy je tak, by zachować następującą własność:

• Jeżeli dostaliśmy wcześniej odpowiedź $\mathtt{\text{\%}}$ 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ź $\mathtt{\text{\%}}$; i wartość $\lfloor x/Q\rfloor$ dla najmniejszego $Q$, dla którego dostaliśmy tę odpowiedź. Zauważmy, że jeśli $P\ge 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\le 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\le 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ź.