Universal Cup Judging System

Universal Cup

Süre Sınırı: 1.0 s Bellek Sınırı: 1024 MB Toplam puan: 100 Etkileşimli Hack'lenebilir ✓
İstatistikler

Це інтерактивна задача.

Лінивому Сему та старанній Сарі доручили придумати два цікаві розподіли ймовірностей на множині рядків довжини $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

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.