Universal Cup Judging System

Universal Cup

حد الوقت: 1.0 s حد الذاكرة: 1024 MB مجموع النقاط: 100 تفاعلية قابلة للهجوم ✓
الإحصائيات

Ini adalah masalah interaktif.

Sam yang malas dan Sarah yang rajin ditugaskan untuk membuat dua distribusi peluang yang menarik pada himpunan string dengan panjang $n$ di atas alfabet $\{H, T\}$. Sam yang malas hanya akan melempar koin sebanyak $n$ kali (dengan masing-masing sisi muncul dengan peluang $\frac{1}{2}$; semua lemparan koin saling bebas) lalu menuliskan "H" untuk setiap sisi angka dan "T" untuk setiap sisi gambar. Anda ingin membantu Sarah yang rajin memberi pelajaran kepada Sam yang malas. Anda diberikan sebuah bilangan bulat $t$. Bantulah Sarah membuat suatu distribusi yang $t$-dekat dengan distribusi seragam, sambil membuktikan secara interaktif bahwa Anda dapat membedakan antara distribusi milik Sam yang malas dan Sarah yang rajin dengan akses oracle sepanjang $t$.

Secara formal, untuk suatu bilangan bulat $n$, tinjau himpunan $S = \{H, T\}^n$ berukuran $2^n$, yang terdiri dari semua kemungkinan string dengan panjang $n$ di atas alfabet dua karakter: "H" dan "T". Sebuah distribusi pada himpunan $S$ didefinisikan sebagai sebuah larik bilangan riil tak negatif $\{a_s\}_{s \in S}$ dengan panjang $2^n$ yang diindeks oleh elemen-elemen $S$, sedemikian sehingga jumlah seluruh elemennya sama dengan $1$. Salah satu distribusi paling sederhana adalah distribusi seragam, di mana semua $a_s$ bernilai sama dengan $2^{-n}$.

Untuk sepasang bilangan $\varepsilon \in [0; +\infty)$ dan $k \in \{0, 1, \dots, n\}$, kita katakan bahwa $\{a_s\}_{s \in S}$ adalah distribusi yang $(\varepsilon, k)$-independen jika, untuk setiap pemilihan $k$ indeks $1 \le i_1 < i_2 < \dots < i_k \le n$ dan setiap himpunan bagian $T \subseteq \{H, T\}^k$ dari string-string sepanjang $k$ di atas alfabet $\{H, T\}$, berlaku hal berikut: jumlah dari $a_s$ pada $2^{n-k}|T|$ string $s$ yang upabarisan $s[i_1]s[i_2]\dots s[i_k]$-nya termasuk dalam $T$ berbeda dari $\frac{|T|}{2^k}$ paling banyak sebesar $\varepsilon$. Dalam istilah peluang, hal ini dapat dinyatakan sebagai:

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

Secara intuitif, ini berarti bahwa untuk membedakan distribusi tersebut dari distribusi seragam, Anda harus membedakan peluang yang selisihnya tidak melebihi $\varepsilon$, atau melihat lebih dari $k$ bit dari string yang dihasilkan oleh distribusi tersebut.

Distribusi $\{a_s\}_{s \in S}$ disebut $t$-dekat dengan distribusi seragam jika ia $(2^{-t}t, t)$-independen.

Dalam definisi $(\varepsilon, k)$-independensi, tersirat bahwa Anda harus memilih $k$ indeks terlebih dahulu dan baru kemudian mempelajari distribusi peluang pada $k$ indeks tersebut. Dalam model akses oracle sepanjang $k$, semuanya berbeda. Sebuah string acak dengan panjang $n$ dibangkitkan, lalu $k$ ronde dengan format berikut dilakukan: Anda menyebutkan sebuah bilangan bulat $i \in \{1, 2, \dots, n\}$, dan sebagai respons, Anda akan diberitahu nilai $s[i]$. Anda dapat memutuskan indeks mana yang akan disebutkan berikutnya dengan mempertimbangkan semua pertanyaan yang telah diajukan sebelumnya beserta jawabannya.

Untuk membuktikan bahwa Anda dapat membedakan distribusi Sam yang malas dan Sarah yang rajin, dengan memiliki akses oracle sepanjang $t$ terhadap $m$ string sepanjang $n$ yang diambil sampelnya dari distribusi mereka (masing-masing dibangkitkan secara independen dan seragam dari distribusi Sam yang malas atau distribusi Sarah yang rajin), Anda harus menyimpulkan untuk setiap string dari distribusi siapa string tersebut diambil, dan menebak dengan benar setidaknya $0.75m - 2\sqrt{m}$ kali.

Protokol Interaksi

Baris pertama berisi sebuah bilangan bulat $t$, yang menyatakan tingkat kedekatan yang disyaratkan terhadap distribusi seragam serta panjang akses oracle ($1 \le t \le 5$).

Sebagai respons, cetak sebuah baris berisi satu bilangan bulat $n$, yang menyatakan panjang string yang siap Anda berikan distribusinya beserta bukti interaktif keterbedaannya ($t \le n \le 20$).

Pada baris berikutnya, cetak sebuah baris berisi $2^n$ bilangan bulat $b_s$, yang mendefinisikan distribusi Anda ($0 \le b_s < 2^{64}$; $\sum_{s \in S} b_s > 0$). Berdasarkan data ini, juri akan memilih distribusi $\{a_s\}_{s \in S}$ sesuai aturan $a_s = b_s / \sum_{s \in S} b_s$. Nilai-nilai $b_s$ harus diurutkan berdasarkan urutan leksikografis dari string $s$: sebagai contoh, untuk $n = 3$, bilangan-bilangan tersebut harus dicetak dalam urutan berikut: $b_{HHH}, b_{HHT}, b_{HTH}, b_{HTT}, b_{THH}, b_{THT}, b_{TTH}, b_{TTT}$.

Selanjutnya, baca sebuah bilangan bulat $m$, yang menyatakan banyaknya pemeriksaan interaktif ($1 \le m \le 10^4$). Setelah itu, $m$ pemeriksaan akan disajikan, yang harus diselesaikan satu demi satu.

Pada awal setiap pemeriksaan, juri pertama-tama akan memilih distribusi $\{a_s\}_{s \in S}$ milik Sam yang malas atau Sarah yang rajin dengan peluang $\frac{1}{2}$. Setelah itu, juri mengambil sampel sebuah string acak $s \sim \{a_s\}_{s \in S}$: setiap string $s$ dapat diperoleh dengan peluang $a_s$. Juri kemudian memberi Anda kesempatan untuk mengajukan paling banyak $t$ pertanyaan mengenai karakter-karakter pada string $s$. Untuk mengajukan pertanyaan, cetak sebuah baris berisi bilangan bulat $q \in \{1, 2, \dots, n\}$, yang menyatakan indeks karakter yang ingin diketahui. Setelah itu, baca karakter "H" atau "T" yang merupakan jawaban atas kueri tersebut. Setelah mengajukan dari $0$ hingga $t$ pertanyaan, cetak sebuah baris berisi nama "Sam" jika Anda yakin bahwa $s$ diambil dari distribusi Sam yang malas, atau "Sarah" jika Anda yakin bahwa $s$ diambil dari distribusi Sarah yang rajin. Setelah ini, segera lanjut ke pemeriksaan berikutnya hingga Anda menyelesaikan seluruh $m$ pemeriksaan.

String dapat dicetak dalam huruf besar maupun huruf kecil.

Setelah setiap baris yang dicetak, jangan lupa untuk melakukan flush pada output buffer.

Contoh

Masukan 1

2
3
T
T
T
T
T

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