Universal Cup Judging System

Universal Cup

Limite de temps : 1.0 s Limite de mémoire : 1024 MB Points totaux : 100 Interactif Hackable ✓
Statistiques

呢題係一道交互題。

懶惰嘅 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

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.