呢題係一道交互題。
懶惰嘅 Sam 同勤力嘅 Sarah 被要求喺字母表 $\{H, T\}$ 上面長度為 $n$ 嘅字串集合上面設計兩個有趣嘅概率分佈。懶惰嘅 Sam 只會簡單咁擲 $n$ 次硬幣(每一面出現嘅概率都係 $\frac{1}{2}$;所有擲硬幣事件互相獨立),每次正面向上就寫低 "H",反面向上就寫低 "T"。你想幫勤力嘅 Sarah 教訓一下懶惰嘅 Sam。俾你一個整數 $t$。請幫 Sarah 設計一個同均勻分佈 $t$-接近嘅分佈,同時透過交互方式證明:喺長度為 $t$ 嘅神諭訪問(oracle access)之下,你可以區分懶惰嘅 Sam 同勤力嘅 Sarah 嘅分佈。
形式化咁講,對於某個整數 $n$,考慮大小為 $2^n$ 嘅集合 $S = \{H, T\}^n$,佢由兩個字符 "H" 同 "T" 嘅字母表所構成嘅所有可能長度為 $n$ 嘅字串組成。集合 $S$ 上面嘅一個分佈定義為一個長度為 $2^n$、由非負實數組成嘅陣列 $\{a_s\}_{s \in S}$,以 $S$ 入面嘅元素作為下標,而且佢哋嘅總和等於 $1$。最簡單嘅分佈之一係均勻分佈,其中所有 $a_s$ 都等於 $2^{-n}$。
對於一對數 $\varepsilon \in [0; +\infty)$ 同 $k \in \{0, 1, \dots, n\}$,如果對於任意揀出嘅 $k$ 個下標 $1 \le i_1 < i_2 < \dots < i_k \le n$ 同埋字母表 $\{H, T\}$ 上面長度為 $k$ 嘅字串嘅任意子集 $T \subseteq \{H, T\}^k$,以下條件都成立,咁我哋就話 $\{a_s\}_{s \in S}$ 係一個 $(\varepsilon, k)$-獨立分佈:喺嗰 $2^{n-k}|T|$ 個滿足子序列 $s[i_1]s[i_2]\dots s[i_k]$ 屬於 $T$ 嘅字串 $s$ 上面,$a_s$ 嘅總和同 $\frac{|T|}{2^k}$ 嘅差唔超過 $\varepsilon$。用概率論嘅術語嚟講,可以表示為:
$$\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.$$
直觀咁講,呢個意味住如果要將呢個分佈同均勻分佈區分開嚟,你要麼需要區分相差唔超過 $\varepsilon$ 嘅概率,要麼需要睇呢個分佈產生嘅字串入面超過 $k$ 個位元。
如果分佈 $\{a_s\}_{s \in S}$ 係 $(2^{-t}t, t)$-獨立嘅,就稱佢同均勻分佈係 $t$-接近嘅。
喺 $(\varepsilon, k)$-獨立嘅定義入面,隱含咗你必須首先揀定 $k$ 個下標,然後先至去研究呢 $k$ 個下標上面嘅概率分佈。但係喺長度為 $k$ 嘅神諭訪問模型入面,情況完全唔同。系統會先生成一個長度為 $n$ 嘅隨機字串,然後進行 $k$ 輪如下格式嘅交互:你指定一個整數 $i \in \{1, 2, \dots, n\}$,作為回應,你會被告知 $s[i]$。你可以考慮之前問過嘅所有問題同埋佢哋嘅答案,嚟決定下一步查詢邊個下標。
為咗證明你可以區分懶惰嘅 Sam 同勤力嘅 Sarah 嘅分佈,你需要喺擁有長度為 $t$ 嘅神諭訪問權限下,對從佢哋嘅分佈入面抽樣出嚟嘅 $m$ 個長度為 $n$ 嘅字串(每個字串都係獨立而且等概率咁從懶惰嘅 Sam 或者勤力嘅 Sarah 嘅分佈中生成嘅),分別判斷每一個字串係抽自邊個嘅分佈,並且至少猜中 $0.75m - 2\sqrt{m}$ 次。
交互協定
第一行包含一個整數 $t$,代表同均勻分佈所需嘅接近程度以及神諭訪問嘅長度($1 \le t \le 5$)。
作為回應,請輸出一行包含一個整數 $n$,代表你準備提供分佈同埋可區分性交互證明嘅字串長度($t \le n \le 20$)。
喺下一行,輸出包含 $2^n$ 個整數 $b_s$ 嘅一行,用嚟定義你嘅分佈($0 \le b_s < 2^{64}$; $\sum_{s \in S} b_s > 0$)。根據呢啲數據,評測機將會按照規則 $a_s = b_s / \sum_{s \in S} b_s$ 揀定分佈 $\{a_s\}_{s \in S}$。$b_s$ 嘅值必須按照字串 $s$ 嘅字典序排列:例如當 $n = 3$ 時,數字應該按以下順序輸出:$b_{HHH}, b_{HHT}, b_{HTH}, b_{HTT}, b_{THH}, b_{THT}, b_{TTH}, b_{TTT}$。
跟住,讀入一個整數 $m$,代表交互測試嘅次數($1 \le m \le 10^4$)。之後會依次進行 $m$ 次測試,需要逐一完成。
喺每次測試開始時,評測機會先以 $\frac{1}{2}$ 嘅概率揀選懶惰嘅 Sam 或者勤力嘅 Sarah 嘅分佈 $\{a_s\}_{s \in S}$。之後,評測機會抽樣一個隨機字串 $s \sim \{a_s\}_{s \in S}$:每個字串 $s$ 被抽中嘅概率為 $a_s$。然後評測機會俾你機會去對字串 $s$ 嘅字符提出唔超過 $t$ 個問題。要提出問題,請輸出一行包含一個整數 $q \in \{1, 2, \dots, n\}$,代表你想查詢嘅字符下標。之後,讀入字符 "H" 或者 "T" 作為該查詢嘅回答。喺問咗 $0$ 到 $t$ 個問題之後,如果你認為 $s$ 係來自懶惰嘅 Sam 嘅分佈,請輸出一行名字 "Sam";如果你認為 $s$ 係來自勤力嘅 Sarah 嘅分佈,請輸出一行名字 "Sarah"。之後即刻進入下一次測試,直到完成晒全部 $m$ 次測試為止。
輸出嘅字串唔區分大小寫。
喺每次輸出一行之後,千祈唔好忘記刷新輸出緩衝區(flush)。
範例
範例輸入 1
2 3 T T T T T
範例輸出 1
3 7 4 8 9 7 6 7 1 1 2 SAM 1 2 Sarah 3 sARaH