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

Þetta er gagnvirkt verkefni.

Lata Sam og duglegu Söruh hefur verið falið að finna upp tvær áhugaverðar líkindadreifingar yfir mengi strengja af lengd $n$ yfir stafrófið $\{H, T\}$. Lati Sam mun einfaldlega kasta peningi $n$ sinnum (þar sem hvor hlið kemur upp með líkunum $\frac{1}{2}$; öll peningaköstin eru óháð) og skrifa niður „H“ fyrir hvertหัว (þorsk) og „T“ fyrir hverja skjaldarmerkishlið (krónu). Þú vilt hjálpa duglegu Söruh að kenna lata Sam lexíu. Þér er gefin heiltala $t$. Hjálpaðu Söruh að finna upp dreifingu sem er $t$-nálægt jafndreifingunni, á meðan þú sannar gagnvirkt að þú getir greint á milli dreifinga lata Sams og duglegu Söruh með véfréttaraðgangi (oracle access) af lengd $t$.

Formlega, fyrir einhverja heiltölu $n$, skoðum mengið $S = \{H, T\}^n$ af stærð $2^n$, sem samanstendur af öllum mögulegum strengjum af lengd $n$ yfir stafrófið með tveimur stöfum: „H“ og „T“. Dreifing yfir mengið $S$ er skilgreind sem fylki af óneikvæðum rauntölum $\{a_s\}_{s \in S}$ af lengd $2^n$ vísað með stökum $S$, þannig að summa þeirra sé jöfn $1$. Ein einfaldasta dreifingin er jafndreifingin, þar sem öll $a_s$ eru jöfn $2^{-n}$.

Fyrir tvennd talna $\varepsilon \in [0; +\infty)$ og $k \in \{0, 1, \dots, n\}$ segjum við að $\{a_s\}_{s \in S}$ sé $(\varepsilon, k)$-óháð dreifing ef, fyrir sérhvert val á $k$ vísum $1 \le i_1 < i_2 < \dots < i_k \le n$ og sérhvert hlutmengi $T \subseteq \{H, T\}^k$ strengja af lengd $k$ yfir stafrófið $\{H, T\}$, eftirfarandi gildir: summa $a_s$ yfir þá $2^{n-k}|T|$ strengi $s$ sem hafa hlutrununa $s[i_1]s[i_2]\dots s[i_k]$ í $T$ víkur frá $\frac{|T|}{2^k}$ um í mesta lagi $\varepsilon$. Með líkindafræðilegum hætti má setja þetta fram sem:

$$\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.$$

Innsæið segir okkur að til að greina dreifinguna frá jafndreifingu þurfir þú annaðhvort að greina á milli líkinda þar sem munurinn fer ekki yfir $\varepsilon$, eða skoða fleiri en $k$ bita í strengjunum sem dreifingin framleiðir.

Dreifingin $\{a_s\}_{s \in S}$ kallast $t$-nálægt jafndreifingunni ef hún er $(2^{-t}t, t)$-óháð.

Í skilgreiningunni á $(\varepsilon, k)$-óhæði fólst í raun að þú yrðir fyrst að velja $k$ vísa og aðeins þá skoða líkindadreifinguna á þessum $k$ vísum. Í líkaninu með véfréttaraðgangi af lengd $k$ er allt öðruvísi. Handahófskenndur strengur af lengd $n$ er búinn til og síðan eru $k$ umferðir með eftirfarandi sniði framkvæmdar: þú nefnir heiltölu $i \in \{1, 2, \dots, n\}$, og sem svar færðu að vita $s[i]$. Þú getur ákveðið hvaða vísi þú nefnir næst með hliðsjón af öllum fyrri spurningum og svörum við þeim.

Til að sanna að þú getir greint á milli dreifinga lata Sams og duglegu Söruh þarftu, með véfréttaraðgangi af lengd $t$ að $m$ strengjum af lengd $n$ sem teknir eru úr dreifingum þeirra (hver um sig búinn til óháð og jafndreift úr annaðhvort dreifingu lata Sams eða duglegu Söruh), að álykta fyrir hvern þeirra úr hvors dreifingu hann var tekinn, og giska rétt að minnsta kosti $0.75m - 2\sqrt{m}$ sinnum.

Samskiptareglur

Fyrsta línan inniheldur heiltölu $t$, sem táknar مطلوبa nálægð við jafndreifingu og lengd véfréttaraðgangsins ($1 \le t \le 5$).

Sem svar skaltu prenta línu með einni heiltölu $n$, sem táknar lengd strengjanna sem þú ert tilbúin(n) að gefa upp dreifingu fyrir og gagnvirka sönnun á aðgreinanleika ($t \le n \le 20$).

Á næstu línu skaltu prenta línu með $2^n$ heiltölum $b_s$, sem skilgreina dreifinguna þína ($0 \le b_s < 2^{64}$; $\sum_{s \in S} b_s > 0$). Byggt á þessum gögnum mun dómnefndin velja dreifinguna $\{a_s\}_{s \in S}$ samkvæmt reglunni $a_s = b_s / \sum_{s \in S} b_s$. Gildin á $b_s$ verða að vera talin upp í stafrófsröð (lexicographical order) strengjanna $s$: til dæmis, fyrir $n = 3$, ættu tölurnar að prentast í eftirfarandi röð: $b_{HHH}, b_{HHT}, b_{HTH}, b_{HTT}, b_{THH}, b_{THT}, b_{TTH}, b_{TTT}$.

Næst skaltu lesa heiltölu $m$, sem táknar fjölda gagnvirkra prófana ($1 \le m \le 10^4$). Í kjölfarið verða $m$ prófanir lagðar fyrir, sem þarf að ljúka einni af annarri.

Í upphafi hverrar prófunar mun dómnefndin fyrst velja dreifinguna $\{a_s\}_{s \in S}$ annaðhvort frá lata Sam eða duglegu Söruh með líkunum $\frac{1}{2}$. Eftir það tekur dómnefndin slembiúrtak $s \sim \{a_s\}_{s \in S}$: sérhver strengur $s$ getur fengist með líkunum $a_s$. Dómnefndin gefur þér síðan tækifæri til að spyrja ekki fleiri en $t$ spurninga um stafina í strengnum $s$. Til að spyrja spurningar skaltu prenta línu með heiltölu $q \in \{1, 2, \dots, n\}$, sem táknar vísi stafsins sem þú hefur áhuga á. Eftir það skaltu lesa stafinn „H“ eða „T“ sem er svarið við fyrirspurninni. Eftir að hafa spurt frá $0$ til $t$ spurninga skaltu prenta línu með nafninu „Sam“ ef þú telur að $s$ hafi verið tekinn úr dreifingu lata Sams, eða „Sarah“ ef þú telur að $s$ hafi verið tekinn úr dreifingu duglegu Söruh. Eftir þetta skaltu halda strax áfram í næstu prófun þar til þú hefur lokið öllum $m$.

Strengi má prenta með hástöfum eða lágstöfum.

Eftir hverja prentaða línu, ekki gleyma að tæma úttaksbiðminnið (flush).

Dæmi

Inntak 1

2
3
T
T
T
T
T

Úttak 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.