Бұл интерактивті есеп.
Жалқау Сэм мен еңбекқор Сараға $\{H, T\}$ әліпбиі үстіндегі ұзындығы $n$ болатын жолдар жиынында екі қызықты ықтималдық үлестірімін ойлап табу тапсырылды. Жалқау Сэм жай ғана тиынды $n$ рет лақтырады (әр жағының түсу ықтималдығы $\frac{1}{2}$; барлық тиын лақтырулар өзара тәуелсіз) және әрбір бүк (head) үшін «H», ал әрбір шік (tail) үшін «T» деп жазады. Сіз еңбекқор Сараға жалқау Сэмді сабасына түсіруге көмектескіңіз келеді. Сізге бүтін сан $t$ берілген. Сараға бірқалыпты үлестірімге $t$-жақын үлестірім ойлап табуға көмектесіңіз, сонымен бірге ұзындығы $t$ болатын оракулдық қол жеткізу арқылы жалқау Сэм мен еңбекқор Сараның үлестірімдерін ажырата алатыныңызды интерактивті түрде дәлелдеңіз.
Формалды түрде, қандай да бір бүтін $n$ саны үшін «H» және «T» деген екі таңбадан тұратын әліпби үстіндегі ұзындығы $n$ болатын барлық мүмкін жолдардан құралған өлшемі $2^n$ болатын $S = \{H, T\}^n$ жиынын қарастырайық. $S$ жиынындағы үлестірім деп элементтері $S$ жиынының элементтерімен индекстелген, қосындысы $1$-ге тең, ұзындығы $2^n$ болатын теріс емес нақты сандар массиві $\{a_s\}_{s \in S}$ аталады. Ең қарапайым үлестірімдердің бірі — барлық $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)$-тәуелсіз үлестірім деп атаймыз: $s[i_1]s[i_2]\dots s[i_k]$ ішкі тізбегі $T$-ға тиісті болатын $2^{n-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]$ хабарланады. Бұрын қойылған барлық сұрақтар мен олардың жауаптарын ескере отырып, келесіде қай индексті шақыру керектігін шеше аласыз.
Жалқау Сэм мен еңбекқор Сараның үлестірімдерін ажырата алатыныңызды дәлелдеу үшін, сізге олардың үлестірімдерінен алынған ұзындығы $n$ болатын $m$ жолға (әрқайсысы тәуелсіз және тең ықтималдықпен не жалқау Сэмнің, не еңбекқор Сараның үлестірімінен генерацияланған) ұзындығы $t$ болатын оракулдық қол жеткізуді пайдалана отырып, олардың әрқайсысы үшін кімнің үлестірімінен алынғаны туралы қорытынды жасап, кем дегенде $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}$ ықтималдықпен жалқау Сэмнің немесе еңбекқор Сараның $\{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» есімі бар жолды, ал егер $s$ еңбекқор Сараның үлестірімінен алынды деп есептесеңіз, «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