To jest zadanie interaktywne.
Leniwy Sam i pilna Sarah otrzymali zadanie wymyślenia dwóch ciekawych rozkładów prawdopodobieństwa na zbiorze napisów długości $n$ nad alfabetem $\{H, T\}$. Leniwy Sam po prostu rzuci monetą $n$ razy (każda strona wypada z prawdopodobieństwem $\frac{1}{2}$; wszystkie rzuty monetą są niezależne) i zapisze „H” dla każdego orła oraz „T” dla każdej reszki. Chcesz pomóc pilnej Sarah dać leniwemu Samowi nauczkę. Dana jest liczba całkowita $t$. Pomóż Sarah wymyślić rozkład, który jest $t$-bliski rozkładowi jednostajnemu, jednocześnie interaktywnie udowadniając, że potrafisz rozróżnić rozkłady leniwego Sama i pilnej Sarah przy dostępie do wyroczni o długości $t$.
Formalnie, dla pewnej liczby całkowitej $n$, rozważmy zbiór $S = \{H, T\}^n$ rozmiaru $2^n$, składający się ze wszystkich możliwych napisów długości $n$ nad alfabetem złożonym z dwóch znaków: „H” oraz „T”. Rozkład na zbiorze $S$ jest zdefiniowany jako tablica nieujemnych liczb rzeczywistych $\{a_s\}_{s \in S}$ długości $2^n$, indeksowana elementami zbioru $S$, taka że ich suma wynosi $1$. Jednym z najprostszych rozkładów jest rozkład jednostajny, w którym wszystkie $a_s$ są równe $2^{-n}$.
Dla pary liczb $\varepsilon \in [0; +\infty)$ oraz $k \in \{0, 1, \dots, n\}$ mówimy, że $\{a_s\}_{s \in S}$ jest rozkładem $(\varepsilon, k)$-niezależnym, jeśli dla każdego wyboru $k$ indeksów $1 \le i_1 < i_2 < \dots < i_k \le n$ oraz każdego podzbioru $T \subseteq \{H, T\}^k$ napisów długości $k$ nad alfabetem $\{H, T\}$ zachodzi następujący warunek: suma wartości $a_s$ po $2^{n-k}|T|$ napisach $s$, których podciąg $s[i_1]s[i_2]\dots s[i_k]$ należy do $T$, różni się od $\frac{|T|}{2^k}$ o co najwyżej $\varepsilon$. W terminologii rachunku prawdopodobieństwa można to zapisać jako:
$$\forall 1 \le i_1 < i_2 < \dots < i_k \le n \quad \forall T \subseteq \{H, T\}^k \quad \frac{|T|}{2^k} - \varepsilon \le \mathbb{P}_{s \leftarrow \{a_s\}_{s \in S}} \{s[i_1]s[i_2]\dots s[i_k] \in T\} \le \frac{|T|}{2^k} + \varepsilon.$$
Intuicyjnie oznacza to, że aby odróżnić ten rozkład od rozkładu jednostajnego, trzeba albo rozróżnić prawdopodobieństwa różniące się o co najwyżej $\varepsilon$, albo spojrzeć na więcej niż $k$ bitów napisów generowanych przez ten rozkład.
Rozkład $\{a_s\}_{s \in S}$ nazywamy $t$-bliskim rozkładowi jednostajnemu, jeśli jest on $(2^{-t}t, t)$-niezależny.
W definicji $(\varepsilon, k)$-niezależności milcząco założono, że najpierw należy wybrać $k$ indeksów, a dopiero potem badać rozkład prawdopodobieństwa na tych $k$ indeksach. W modelu dostępu do wyroczni o długości $k$ wszystko wygląda inaczej. Generowany jest losowy napis długości $n$, a następnie przeprowadzanych jest $k$ rund w następującym formacie: podajesz liczbę całkowitą $i \in \{1, 2, \dots, n\}$, a w odpowiedzi dowiadujesz się, ile wynosi $s[i]$. Możesz zdecydować, który indeks wywołać jako następny, biorąc pod uwagę wszystkie wcześniej zadane pytania i uzyskane na nie odpowiedzi.
Aby udowodnić, że potrafisz rozróżnić rozkłady leniwego Sama i pilnej Sarah, mając dostęp do wyroczni o długości $t$ dla $m$ napisów długości $n$ wylosowanych z ich rozkładów (każdy wygenerowany niezależnie i jednostajnie z rozkładu leniwego Sama lub pilnej Sarah), będziesz musiał dla każdego z nich orzec, z czyjego rozkładu został pobrany, i odgadnąć poprawnie co najmniej $0.75m - 2\sqrt{m}$ razy.
Protokół interakcji
Pierwszy wiersz zawiera liczbę całkowitą $t$, oznaczającą wymaganą bliskość do rozkładu jednostajnego oraz długość dostępu do wyroczni ($1 \le t \le 5$).
W odpowiedzi wypisz wiersz z jedną liczbą całkowitą $n$, oznaczającą długość napisów, dla których jesteś gotów podać rozkład oraz interaktywny dowód rozróżnialności ($t \le n \le 20$).
W następnym wierszu wypisz $2^n$ liczb całkowitych $b_s$, definiujących Twój rozkład ($0 \le b_s < 2^{64}$; $\sum_{s \in S} b_s > 0$). Na podstawie tych danych jury wybierze rozkład $\{a_s\}_{s \in S}$ zgodnie z regułą $a_s = b_s / \sum_{s \in S} b_s$. Wartości $b_s$ muszą zostać wypisane w porządku leksykograficznym napisów $s$: na przykład dla $n = 3$ liczby powinny zostać wypisane w następującej kolejności: $b_{HHH}, b_{HHT}, b_{HTH}, b_{HTT}, b_{THH}, b_{THT}, b_{TTH}, b_{TTT}$.
Następnie wczytaj liczbę całkowitą $m$, oznaczającą liczbę testów interaktywnych ($1 \le m \le 10^4$). Po tym nastąpi $m$ testów, które należy wykonać jeden po drugim.
Na początku każdego testu jury najpierw wybierze rozkład $\{a_s\}_{s \in S}$ leniwego Sama lub pilnej Sarah z prawdopodobieństwem $\frac{1}{2}$. Następnie jury losuje napis $s \sim \{a_s\}_{s \in S}$: każdy napis $s$ może zostać wylosowany z prawdopodobieństwem $a_s$. Potem jury daje Ci możliwość zadania co najwyżej $t$ pytań o znaki napisu $s$. Aby zadać pytanie, wypisz wiersz z liczbą całkowitą $q \in \{1, 2, \dots, n\}$, oznaczającą indeks interesującego Cię znaku. Następnie wczytaj znak „H” lub „T”, będący odpowiedzią na zapytanie. Po zadaniu od $0$ do $t$ pytań wypisz wiersz z imieniem „Sam”, jeśli uważasz, że napis $s$ został pobrany z rozkładu leniwego Sama, lub „Sarah”, jeśli uważasz, że $s$ pochodzi z rozkładu pilnej Sarah. Po tym natychmiast przejdź do kolejnego testu, aż ukończysz wszystkie $m$ testów.
Napisy mogą być wypisywane literami dowolnej wielkości.
Po każdym wypisanym wierszu nie zapomnij opróżnić bufora wyjścia (flush).
Przykład
Wejście 1
2 3 T T T T T
Wyjście 1
3 7 4 8 9 7 6 7 1 1 2 SAM 1 2 Sarah 3 sARaH