Universal Cup Judging System

Universal Cup

実行時間制限: 1.0 s メモリ制限: 1024 MB 満点: 100 インタラクティブ ハック可能 ✓
統計

Tämä on vuorovaikutteinen tehtävä.

Laiska Sam ja ahkera Sarah ovat saaneet tehtäväkseen keksiä kaksi mielenkiintoista todennäköisyysjakaumaa aakkoston $\{H, T\}$ pituutta $n$ olevien merkkijonojen joukolle. Laiska Sam yksinkertaisesti heittää kolikkoa $n$ kertaa (kumpikin puoli esiintyy todennäköisyydellä $\frac{1}{2}$; kaikki kolikonheitot ovat riippumattomia) ja kirjoittaa ”H” jokaisesta kruunasta ja ”T” jokaisesta klaavasta. Haluat auttaa ahkeraa Sarahia antamaan laiskalle Samille opetuksen. Sinulle annetaan kokonaisluku $t$. Auta Sarahia keksimään jakauma, joka on $t$-lähellä tasajakaumaa, samalla kun todistat vuorovaikutteisesti, että pystyt erottamaan laiskan Samin ja ahkeran Sarahin jakaumat toisistaan pituuden $t$ oraakkelipääsyllä.

Muodollisesti, jollekin kokonaisluvulle $n$, tarkastellaan kokoa $2^n$ olevaa joukkoa $S = \{H, T\}^n$, joka koostuu kaikista mahdollisista pituuden $n$ merkkijonoista kahden merkin ”H” ja ”T” aakkostolla. Jakauma joukolla $S$ määritellään joukon $S$ alkioilla indeksoiduksi pituuden $2^n$ ei-negatiivisten reaalilukujen taulukoksi $\{a_s\}_{s \in S}$, jolle lukujen summa on $1$. Yksi yksinkertaisimmista jakaumista on tasajakauma, jossa kaikki $a_s$ ovat yhtä suuria kuin $2^{-n}$.

Lukuparille $\varepsilon \in [0; +\infty)$ ja $k \in \{0, 1, \dots, n\}$ sanomme, että $\{a_s\}_{s \in S}$ on $(\varepsilon, k)$-riippumaton jakauma, jos mille tahansa $k$:n indeksin valinnalle $1 \le i_1 < i_2 < \dots < i_k \le n$ ja mille tahansa aakkoston $\{H, T\}$ pituuden $k$ merkkijonojen osajoukolle $T \subseteq \{H, T\}^k$ pätee seuraava: lukujen $a_s$ summa niiden $2^{n-k}|T|$ merkkijonon $s$ yli, joiden osajono $s[i_1]s[i_2]\dots s[i_k]$ kuuluu joukkoon $T$, poikkeaa arvosta $\frac{|T|}{2^k}$ enintään $\varepsilon$. Todennäköisyyslaskennan termein tämä voidaan ilmaista muodossa:

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

Intuitiivisesti tämä tarkoittaa, että erottaaksesi jakauman tasajakaumasta sinun täytyy joko erottaa todennäköisyydet, joiden erotus on enintään $\varepsilon$, tai tarkastella useampaa kuin $k$:ta bittiä jakauman tuottamissa merkkijonoissa.

Jakaumaa $\{a_s\}_{s \in S}$ kutsutaan $t$-läheiseksi tasajakauman kanssa, jos se on $(2^{-t}t, t)$-riippumaton.

$(\varepsilon, k)$-riippumattomuuden määritelmässä oletettiin epäsuorasti, että sinun on ensin valittava $k$ indeksiä ja vasta sitten tutkittava todennäköisyysjakaumaa näillä $k$:lla indeksillä. Pituuden $k$ oraakkelipääsymallissa kaikki on toisin. Luodaan satunnainen pituuden $n$ merkkijono, ja sen jälkeen suoritetaan $k$ kierrosta seuraavassa muodossa: ilmoitat kokonaisluvun $i \in \{1, 2, \dots, n\}$, ja vastauksena sinulle kerrotaan $s[i]$. Voit päättää, mitä indeksiä kysyt seuraavaksi, ottaen huomioon kaikki aiemmin esitetyt kysymykset ja niiden vastaukset.

Todistaaksesi, että pystyt erottamaan laiskan Samin ja ahkeran Sarahin jakaumat, sinun tulee – kun käytössäsi on pituuden $t$ oraakkelipääsy heidän jakaumistaan poimittuun $m$:ään pituuden $n$ merkkijonoon (joista jokainen on luotu riippumattomasti ja tasajakautuneesti joko laiskan Samin tai ahkeran Sarahin jakaumasta) – päätellä jokaisesta niistä, kumman jakaumasta se on otettu, ja arvata oikein vähintään $0.75m - 2\sqrt{m}$ kertaa.

Vuorovaikutusprotokolla

Ensimmäinen rivi sisältää kokonaisluvun $t$, joka ilmaisee vaaditun läheisyyden tasajakaumaan sekä oraakkelipääsyn pituuden ($1 \le t \le 5$).

Tulosta vastauksena rivi, jolla on yksi kokonaisluku $n$, joka ilmaisee niiden merkkijonojen pituuden, joille olet valmis antamaan jakauman ja vuorovaikutteisen todistuksen erotettavuudesta ($t \le n \le 20$).

Tulosta seuraavalle riville $2^n$ kokonaislukua $b_s$, jotka määrittelevät jakaumasi ($0 \le b_s < 2^{64}$; $\sum_{s \in S} b_s > 0$). Näiden tietojen perusteella tuomaristo valitsee jakauman $\{a_s\}_{s \in S}$ säännön $a_s = b_s / \sum_{s \in S} b_s$ mukaisesti. Lukujen $b_s$ arvot on lueteltava merkkijonojen $s$ aakkosjärjestyksessä: esimerkiksi kun $n = 3$, luvut tulee tulostaa seuraavassa järjestyksessä: $b_{HHH}, b_{HHT}, b_{HTH}, b_{HTT}, b_{THH}, b_{THT}, b_{TTH}, b_{TTT}$.

Lue seuraavaksi kokonaisluku $m$, joka ilmaisee vuorovaikutteisten tarkistusten lukumäärän ($1 \le m \le 10^4$). Tämän jälkeen esitetään $m$ tarkistusta, jotka on suoritettava yksi kerrallaan.

Jokaisen tarkistuksen alussa tuomaristo valitsee ensin jakauman $\{a_s\}_{s \in S}$ joko laiskalta Samilta tai ahkeralta Sarahilta todennäköisyydellä $\frac{1}{2}$. Sen jälkeen tuomaristo poimii satunnaisen merkkijonon $s \sim \{a_s\}_{s \in S}$: mikä tahansa merkkijono $s$ voidaan saada todennäköisyydellä $a_s$. Tuomaristo antaa sinulle sitten mahdollisuuden esittää enintään $t$ kysymystä merkkijonon $s$ merkeistä. Esittääksesi kysymyksen tulosta rivi, jolla on kokonaisluku $q \in \{1, 2, \dots, n\}$, joka ilmaisee haluamasi merkin indeksin. Lue sen jälkeen merkki ”H” tai ”T”, joka on vastaus kyselyyn. Esitettyäsi $0$ – $t$ kysymystä tulosta rivi, jolla on nimi ”Sam”, jos uskot merkkijonon $s$ olevan peräisin laiskan Samin jakaumasta, tai ”Sarah”, jos uskot merkkijonon $s$ olevan peräisin ahkeran Sarahin jakaumasta. Siirry tämän jälkeen välittömästi seuraavaan tarkistukseen, kunnes olet suorittanut kaikki $m$.

Merkkijonot voidaan tulostaa isoilla tai pienillä kirjaimilla.

Muista tyhjentää tulostepuskuri (flush) jokaisen tulostetun rivin jälkeen.

Esimerkki

Syöte 1

2
3
T
T
T
T
T

Tuloste 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.