Alice i jej młodszy brat, Bob, grają w grę polegającą na odgadywaniu liczby.
Bob wybrał (ukrytą) liczbę całkowitą $S$.
Alice może zadawać pytania dotyczące ukrytej liczby w następującej formie: "Czy ukryta liczba wynosi co najmniej $x$?". Bob odpowiada na jej pytania "Tak" lub "Nie". Niestety, po $K \ge 1$ pytaniach, Bob nudzi się grą i od tego momentu udziela fałszywych odpowiedzi na wszystkie pytania.
Oznacza to, że Bob: Odpowiada "Tak" na pierwsze $K$ pytań wtedy i tylko wtedy, gdy $x \le S$. Po $K$-tym pytaniu odpowiada "Tak" wtedy i tylko wtedy, gdy $S < x$.
Zauważ, że Bob zawsze odpowiada poprawnie na pierwsze pytanie, a Alice nie zna wartości $K$.
Twoim zadaniem jest opracowanie i zaimplementowanie strategii zadawania pytań przez Alice, aby zidentyfikować ukrytą liczbę. Twój wynik zależy od liczby zadanych pytań – im mniej pytań, tym lepszy wynik.
Szczegóły implementacji
Powinieneś zaimplementować następującą procedurę:
long long play_game()- Ta procedura jest wywoływana co najwyżej $T$ razy dla każdego zestawu testowego.
Procedura powinna znaleźć i zwrócić ukrytą liczbę $S$, wywołując następującą procedurę, aby zadać pytania dotyczące ukrytej liczby:
bool ask(long long x)- $x$: liczba określająca pytanie Alice.
- Wartość $x$ musi mieścić się w przedziale od $1$ do $10^{18}$ włącznie.
- Procedura zwraca wartość logiczną reprezentującą odpowiedź Boba.
- Procedura może zostać wywołana co najwyżej $150$ razy w każdym wywołaniu
play_game.
Zachowanie sprawdzaczki jest adaptacyjne, co oznacza, że w niektórych testach wartości $S$ i $K$ nie są ustalone przed wywołaniem play_game. Gwarantuje się, że istnieje co najmniej jedna para $(S, K)$, dla której odpowiedzi sprawdzaczki są spójne.
Ograniczenia
- $1 \le T \le 1000$
- $1 \le S \le 10^{18}$
- $1 \le K \le 150$
Podzadania
Jeśli Twoje rozwiązanie nie jest zgodne z powyższymi szczegółami implementacji lub jeśli wartość zwrócona przez play_game jest niepoprawna nawet dla pojedynczego wywołania, Twoje rozwiązanie otrzyma 0 punktów.
W przeciwnym razie, niech $C$ będzie maksymalną liczbą pytań, które Twoje rozwiązanie zadaje we wszystkich wywołaniach play_game. Twój wynik jest obliczany zgodnie z poniższą tabelą:
| Warunek | Punkty |
|---|---|
| $132 < C \le 150$ | $20 \cdot (\frac{150-C}{18})^2$ |
| $78 < C \le 132$ | $20 + 20 \cdot (\frac{132-C}{54})^2$ |
| $72 < C \le 78$ | $40 + 30 \cdot (\frac{78-C}{6})^2$ |
| $67 < C \le 72$ | $70 + 30 \cdot (\frac{72-C}{5})^2$ |
| $C \le 67$ | $100$ |
Przykład
Rozważmy scenariusz, w którym ukryta liczba całkowita to $S = 2$, a $K = 1$. Gra rozpoczyna się od wywołania:
play_game()
Załóżmy, że play_game najpierw wywołuje ask(2). Ponieważ $2 \le S = 2$ i Bob mówi w tym momencie prawdę, wywołanie zwraca true.
Załóżmy, że play_game wywołuje ask(2) ponownie. Chociaż warunek $2 \le S = 2$ nadal jest spełniony, Bob teraz kłamie (po udzieleniu prawdziwej odpowiedzi $K = 1$ raz), więc wywołanie zwraca false. Otrzymanie sprzecznych odpowiedzi na to samo pytanie ujawnia, że Bob będzie kłamał na wszystkie kolejne pytania.
Teraz załóżmy, że play_game wywołuje ask(3). Ponieważ $3 \le S = 2$ jest fałszem, a Bob kłamie, wywołanie zwraca true. W tym momencie możemy wywnioskować, że $2 \le S < 3$, co oznacza $S = 2$.
Dlatego procedura powinna zwrócić $2$.
Przykładowa sprawdzaczka
Przykładowa sprawdzaczka nie jest adaptacyjna. Przetwarza $T$ scenariuszy i w każdym przypadku odczytuje ustalone wartości $S$ i $K$ z wejścia, odpowiadając na pytania zgodnie z nimi.
Wejście:
T S[0] K[0] S[1] K[1] ... S[T-1] K[T-1]
Tutaj $S[i]$ oraz $K[i]$ ($0 \le i < T$) określają ukryte parametry dla każdego wywołania play_game.
Wyjście:
G[0] C[0] G[1] C[1] ... G[T-1] C[T-1]
Tutaj $G[i]$ ($0 \le i < T$) to liczba zwrócona przez play_game, gdy ukryte parametry to $S[i]$ i $K[i]$, a $C[i]$ to liczba pytań zadanych podczas tego wywołania.