Universal Cup Judging System

Universal Cup

Límite de tiempo: 1.0 s Límite de memoria: 1024 MB Puntuación total: 100 Interactivo Hackeable ✓
Estadísticas

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

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1215EditorialOpen题解jianglyView

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.