Это интерактивная задача.
Ленивому Сэму и прилежной Саре поручили придумать два интересных распределения вероятностей на множестве строк длины $n$ над алфавитом $\{H, T\}$. Ленивый Сэм просто подбросит монетку $n$ раз (каждая сторона выпадает с вероятностью $\frac{1}{2}$; все броски независимы) и запишет «H» для каждого орла и «T» для каждой решки. Вы хотите помочь прилежной Саре проучить ленивого Сэма. Вам дано целое число $t$. Помогите Саре придумать распределение, которое является $t$-близким к равномерному распределению, и одновременно интерактивно докажите, что вы можете различить распределения ленивого Сэма и прилежной Сары при помощи оракульного доступа длины $t$.
Формально, для некоторого целого числа $n$ рассмотрим множество $S = \{H, T\}^n$ размера $2^n$, состоящее из всех возможных строк длины $n$ над алфавитом из двух символов: «H» и «T». Распределение на множестве $S$ определяется как массив неотрицательных вещественных чисел $\{a_s\}_{s \in S}$ длины $2^n$, индексированный элементами множества $S$, сумма которых равна $1$. Одним из простейших распределений является равномерное распределение, в котором все $a_s$ равны $2^{-n}$.
Для пары чисел $\varepsilon \in [0; +\infty)$ и $k \in \{0, 1, \dots, n\}$ мы говорим, что $\{a_s\}_{s \in S}$ является $(\varepsilon, k)$-независимым распределением, если для любого набора из $k$ индексов $1 \le i_1 < i_2 < \dots < i_k \le n$ и любого подмножества $T \subseteq \{H, T\}^k$ строк длины $k$ над алфавитом $\{H, T\}$ выполняется следующее: сумма $a_s$ по $2^{n-k}|T|$ строкам $s$, у которых подпоследовательность $s[i_1]s[i_2]\dots s[i_k]$ принадлежит $T$, отличается от $\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}$ называется $t$-близким к равномерному распределению, если оно является $(2^{-t}t, t)$-независимым.
В определении $(\varepsilon, k)$-независимости подразумевалось, что вы должны сначала выбрать $k$ индексов и только затем изучать распределение вероятностей на этих $k$ индексах. В модели оракульного доступа длины $k$ всё иначе. Генерируется случайная строка длины $n$, а затем проводится $k$ раундов следующего вида: вы называете целое число $i \in \{1, 2, \dots, n\}$, а в ответ вам сообщают $s[i]$. Вы можете решать, какой индекс назвать следующим, учитывая все ранее заданные вопросы и ответы на них.
Чтобы доказать, что вы можете различить распределения ленивого Сэма и прилежной Сары, вам нужно, имея оракульный доступ длины $t$ к $m$ строкам длины $n$, сэмплированным из их распределений (каждая строка независимо и равновероятно сгенерирована либо из распределения ленивого Сэма, либо из распределения прилежной Сары), для каждой из них сделать вывод, из чьего распределения она была взята, и угадать правильно хотя бы $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\}_{s \in S}$ по правилу $a_s = b_s / \sum_{s \in S} b_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}$ выбирает распределение $\{a_s\}_{s \in S}$ либо ленивого Сэма, либо прилежной Сары. После этого жюри сэмплирует случайную строку $s \sim \{a_s\}_{s \in S}$: любая строка $s$ может быть получена с вероятностью $a_s$. Затем жюри даёт вам возможность задать не более $t$ вопросов о символах строки $s$. Чтобы задать вопрос, выведите строку с целым числом $q \in \{1, 2, \dots, n\}$, обозначающим индекс интересующего вас символа. После этого считайте символ «H» или «T», являющийся ответом на запрос. Задав от $0$ до $t$ вопросов, выведите строку с именем «Sam», если вы считаете, что строка $s$ была взята из распределения ленивого Сэма, или «Sarah», если вы считаете, что $s$ была взята из распределения прилежной Сары. После этого немедленно переходите к следующей проверке, пока не завершите все $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