Universal Cup Judging System

Universal Cup

حد الوقت: 1.0 s حد الذاكرة: 1024 MB مجموع النقاط: 100 تفاعلية قابلة للهجوم ✓
الإحصائيات

Questo è un problema interattivo.

Al pigro Sam e alla diligente Sarah è stato assegnato il compito di ideare due distribuzioni interessanti sull'insieme delle stringhe di lunghezza $n$ sull'alfabeto $\{H, T\}$. Il pigro Sam si limiterà a lanciare una moneta $n$ volte (con ciascuna faccia che esce con probabilità $\frac{1}{2}$; tutti i lanci sono indipendenti) e a scrivere "H" per ogni testa e "T" per ogni croce. Vuoi aiutare la diligente Sarah a dare una lezione al pigro Sam. Ti viene dato un intero $t$. Aiuta Sarah a ideare una distribuzione che sia $t$-vicina alla distribuzione uniforme, dimostrando al contempo in modo interattivo che puoi distinguere tra le distribuzioni del pigro Sam e della diligente Sarah con un accesso all'oracolo di lunghezza $t$.

Formalmente, per un certo intero $n$, considera l'insieme $S = \{H, T\}^n$ di dimensione $2^n$, costituito da tutte le possibili stringhe di lunghezza $n$ sull'alfabeto di due caratteri: "H" e "T". Una distribuzione sull'insieme $S$ è definita come un array di numeri reali non negativi $\{a_s\}_{s \in S}$ di lunghezza $2^n$ indicizzato dagli elementi di $S$, tale che la loro somma sia uguale a $1$. Una delle distribuzioni più semplici è la distribuzione uniforme, in cui tutti gli $a_s$ sono uguali a $2^{-n}$.

Per una coppia di numeri $\varepsilon \in [0; +\infty)$ e $k \in \{0, 1, \dots, n\}$, diciamo che $\{a_s\}_{s \in S}$ è una distribuzione $(\varepsilon, k)$-indipendente se, per qualsiasi scelta di $k$ indici $1 \le i_1 < i_2 < \dots < i_k \le n$ e qualsiasi sottoinsieme $T \subseteq \{H, T\}^k$ di stringhe di lunghezza $k$ sull'alfabeto $\{H, T\}$, vale quanto segue: la somma di $a_s$ sulle $2^{n-k}|T|$ stringhe $s$ la cui sottosequenza $s[i_1]s[i_2]\dots s[i_k]$ appartiene a $T$ differisce da $\frac{|T|}{2^k}$ per non più di $\varepsilon$. In termini probabilistici, ciò può essere espresso come:

$$\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.$$

Intuitivamente, ciò significa che per distinguere la distribuzione da quella uniforme dovrai o distinguere probabilità la cui differenza non supera $\varepsilon$, oppure osservare più di $k$ bit delle stringhe prodotte dalla distribuzione.

La distribuzione $\{a_s\}_{s \in S}$ è detta $t$-vicina alla distribuzione uniforme se è $(2^{-t}t, t)$-indipendente.

Nella definizione di $(\varepsilon, k)$-indipendenza era implicito che si dovessero prima scegliere $k$ indici e solo allora studiare la distribuzione di probabilità su quei $k$ indici. Nel modello di accesso all'oracolo di lunghezza $k$, tutto è diverso. Viene generata una stringa casuale di lunghezza $n$, e poi vengono condotti $k$ turni del seguente formato: tu dichiari un intero $i \in \{1, 2, \dots, n\}$ e, in risposta, ti verrà comunicato $s[i]$. Puoi decidere quale indice chiamare successivamente tenendo conto di tutte le domande poste in precedenza e delle relative risposte.

Per dimostrare che puoi distinguere le distribuzioni del pigro Sam e della diligente Sarah, dovrai, avendo accesso all'oracolo di lunghezza $t$ su $m$ stringhe di lunghezza $n$ campionate dalle loro distribuzioni (ciascuna generata in modo indipendente e uniforme dalla distribuzione del pigro Sam o da quella della diligente Sarah), concludere per ciascuna di esse da quale distribuzione è stata tratta, e indovinare correttamente almeno $0.75m - 2\sqrt{m}$ volte.

Protocollo di interazione

La prima riga contiene un intero $t$, che indica la vicinanza richiesta a una distribuzione uniforme e la lunghezza dell'accesso all'oracolo ($1 \le t \le 5$).

In risposta, stampa una riga con un singolo intero $n$, che indica la lunghezza delle stringhe per le quali sei pronto a fornire la distribuzione e una prova interattiva di distinguibilità ($t \le n \le 20$).

Nella riga successiva, stampa una riga con $2^n$ interi $b_s$, che definiscono la tua distribuzione ($0 \le b_s < 2^{64}$; $\sum_{s \in S} b_s > 0$). Sulla base di questi dati, la giuria sceglierà la distribuzione $\{a_s\}_{s \in S}$ secondo la regola $a_s = b_s / \sum_{s \in S} b_s$. I valori di $b_s$ devono essere elencati nell'ordine lessicografico delle stringhe $s$: ad esempio, per $n = 3$, i numeri devono essere stampati nel seguente ordine: $b_{HHH}, b_{HHT}, b_{HTH}, b_{HTT}, b_{THH}, b_{THT}, b_{TTH}, b_{TTT}$.

Successivamente, leggi un intero $m$, che indica il numero di verifiche interattive ($1 \le m \le 10^4$). In seguito verranno presentate le $m$ verifiche, che dovranno essere completate una dopo l'altra.

All'inizio di ogni verifica, la giuria sceglierà prima la distribuzione $\{a_s\}_{s \in S}$ del pigro Sam oppure della diligente Sarah con probabilità $\frac{1}{2}$. Dopodiché, la giuria campiona una stringa casuale $s \sim \{a_s\}_{s \in S}$: qualsiasi stringa $s$ può essere ottenuta con probabilità $a_s$. La giuria ti dà quindi l'opportunità di porre non più di $t$ domande sui caratteri della stringa $s$. Per porre una domanda, stampa una riga con un intero $q \in \{1, 2, \dots, n\}$, che indica l'indice del carattere di interesse. Dopodiché, leggi il carattere "H" o "T" che rappresenta la risposta alla query. Dopo aver posto da $0$ a $t$ domande, stampa una riga con il nome "Sam" se ritieni che $s$ sia stata presa dalla distribuzione del pigro Sam, oppure "Sarah" se ritieni che $s$ sia stata presa dalla distribuzione della diligente Sarah. Subito dopo, passa alla verifica successiva finché non le avrai completate tutte e $m$.

Le stringhe possono essere stampate indifferentemente in maiuscolo o minuscolo.

Dopo ogni riga stampata, non dimenticare di svuotare il buffer di output (flush).

Esempio

Input 1

2
3
T
T
T
T
T

Output 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.