Universal Cup Judging System

Universal Cup

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

هذه مسألة تفاعلية.

كُلِّف سام الكسول وسارة المجتهدة بابتكار توزيعين احتماليين مثيرين للاهتمام على مجموعة السلاسل النصية التي طولها $n$ على الأبجدية $\{H, T\}$. سيقوم سام الكسول ببساطة برمي عملة معدنية $n$ مرات (حيث يظهر كل وجه باحتمال $\frac{1}{2}$؛ وجميع رميات العملة مستقلة) ويكتب "H" لكل صورة و "T" لكل كتابة. تريد مساعدة سارة المجتهدة في تلقين سام الكسول درساً. يُعطى لك عدد صحيح $t$. ساعد سارة في ابتكار توزيع يكون $t$-قريباً من التوزيع المنتظم، مع إثبات تفاعلي بأنه يمكنك التمييز بين توزيع سام الكسول وتوزيع سارة المجتهدة باستخدام وصول عرّاف (oracle access) بطول $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$ عبر السلاسل $s$ البالغ عددها $2^{n-k}|T|$ والتي تنتمي متتاليتها الجزئية $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$، والتي يجب إكمالها واحداً تلو الآخر.

في بداية كل فحص، ستختار لجنة التحكيم أولاً التوزيع $\{a_s\}_{s \in S}$ إما من سام الكسول أو سارة المجتهدة باحتمال $\frac{1}{2}$. بعد ذلك، تأخذ لجنة التحكيم عينة عشوائية لسلسلة $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.