Universal Cup Judging System

Universal Cup

時間限制: 2.0 s 記憶體限制: 1024 MB 總分: 100 可 Hack ✓
统计

يُعطى لك مصفوفة مكونة من $n$ أعداد صحيحة بين $1$ و $n+1$. من الممكن أن تتكرر بعض الأعداد الصحيحة عدة مرات في المصفوفة. ومع ذلك، من الواضح أن عدداً صحيحاً واحداً على الأقل من الأعداد بين $1$ و $n+1$ مفقود من المصفوفة. مهمتك هي إيجاد أي عدد صحيح من هذا القبيل. في العادة يكون ذلك سهلاً، ولكن هناك مشكلة مؤسفة: لا توجد ذاكرة كافية في حاسوبك لتمثيل المصفوفة بأكملها.

لذلك، يُطلب منك بدلاً من ذلك تصميم خوارزمية تدفقية (streaming algorithm). بشكل غير رسمي، تُعطى لك عناصر المصفوفة واحداً تلو الآخر دون أي طريقة للوصول العشوائي إليها. ومع ذلك، هناك عزاء واحد: بعد استلام العنصر الأخير من المصفوفة، يمكنك إعادة قراءتها من البداية. في الحالة المثالية، تود تجنب مثل هذا الموقف وحل المسألة بأكملها في تمريرة واحدة (one pass). ولكن في بعض الأحيان (بما في ذلك هذه المسألة بالذات) قد يكون إجراء عدة تمريرات على الإدخال ضرورياً لتجنب استخدام قدر كبير جداً من الذاكرة. تحتاج إلى الموازنة بين الأمرين معاً بحيث لا تستخدم الكثير من الذاكرة ولا تجري الكثير من التمريرات على المصفوفة في آنٍ واحد (تصبح المسألة تافهة إذا سُمح لك بتخزين $n$ بت من الذاكرة أو استخدام $n$ تمريرات).

ومع ذلك، لا تزال هناك عقبة واحدة. لأسباب تقنية، تحتاج إلى إنتاج آلة حالات منتهية حتمية (DFA) على الأبجدية $\{0, 1, \dots, n + 1\}$ تُنفذ منطق خوارزميتك. تتوافق رموز الأبجدية مع المعلومات التي تتلقاها عند قراءة التدفق: الأعداد من $1$ إلى $n+1$ تمثل قراءة العدد الصحيح المقابل من المصفوفة، بينما يمثل العدد $0$ حقيقة أنك وصلت إلى نهاية المصفوفة. بعد أول 7 مرات تصل فيها إلى نهاية المصفوفة، ستُعطى لك المصفوفة مرة أخرى بنفس الترتيب السابق، وتنتهي دائماً بالرمز $0$ الذي يمثل نهاية المصفوفة. وبالتالي، سيتم تزويد آلة DFA الخاصة بك بالسلسلة $a_1, a_2, \dots, a_n, 0$ ما مجموعه 8 مرات (هنا، $a_1, a_2, \dots, a_n$ هي المصفوفة المخفية). أخيراً، في أي لحظة من التنفيذ، يمكن لآلتك أن "تعلن" أنها تعرف بالفعل إجابة صحيحة للمسألة؛ وفي هذه الحالة يتوقف التنفيذ. إذا لم تفعل آلة DFA ذلك بحلول الوقت الذي قرأت فيه التدفق بالكامل (بما في ذلك الرمز $0$ في النهاية) 8 مرات، فلن تُقبل كحل. وبالمثل، إذا توقفت ولكن بإجابة خاطئة، فلن تُقبل كحل أيضاً.

لنصغ المسألة بشكل رسمي. توجد مصفوفة مخفية $a_1, a_2, \dots, a_n$ مكونة من $n$ أعداد صحيحة من $1$ إلى $n+1$. في المثال $n = 4$، وفي جميع الاختبارات الأخرى $n = 250$. تحتاج إلى تحديد آلة حالات منتهية تحتوي على ما لا يزيد عن 4000 حالة، مرقمة من $0$ إلى $q - 1$، حيث $q \le 4000$ هو عدد الحالات. بالنسبة للحالة $i$ ($0 \le i \le q - 1$)، تحتاج إلى تحديد $n + 2$ أعداد $\delta(i, 0), \delta(i, 1), \dots, \delta(i, n + 1)$. يمثل العدد $\delta(i, j)$ سلوك آلة DFA عندما تكون في الحالة $i$ وتقرأ العدد $j$ من الإدخال. يجب أن يكون عدداً صحيحاً من $-(n + 1)$ إلى $q - 1$ شاملاً الطرفين. تتوافق الأعداد الصحيحة السالبة مع توقف التنفيذ وإعطاء إجابة؛ وتحديداً، يتوافق $-s$ مع ادعاء آلة DFA أن $+s$ هو إجابة صحيحة للمسألة. تتوافق الأعداد الصحيحة غير السالبة مع استمرار التنفيذ وتغير حالة الآلة من $i$ إلى $\delta(i, j)$. يبدأ تنفيذ الآلة في الحالة $0$.

تُعتبر آلة DFA الخاصة بك تعمل بشكل صحيح على المصفوفة $a_1, a_2, \dots, a_n$ إذا توقفت بإجابة صحيحة عند نقطة ما أثناء قراءة السلسلة $a_1, a_2, \dots, a_n, 0, a_1, a_2, \dots, a_n, 0, \dots, a_1, a_2, \dots, a_n, 0$، حيث تتكرر المصفوفة 8 مرات. وتُعتبر آلة DFA تعمل بشكل صحيح عموماً إذا كانت تعمل بشكل صحيح على جميع المصفوفات الممكنة $a_1, a_2, \dots, a_n$ من الأعداد الصحيحة من $1$ إلى $n+1$ (لذلك، لا يُنصح بالحلول الاحتمالية).

بالنسبة لـ $n = 4$، سنتحقق من آلة DFA الخاصة بك على جميع المصفوفات الممكنة. وبالنسبة لـ $n = 250$، لا نملك وسيلة للتحقق منها على جميع المصفوفات، لذا سنتحقق منها على أقل من 5000 مصفوفة مختارة بعناية. يوجد اختباران في المسألة؛ يتحقق كلا الاختبارين فعلياً من أن طريقتك تعمل بشكل صحيح على العديد من المصفوفات في آنٍ واحد.

الإدخال

عدد صحيح واحد $n$، يساوي إما $4$ أو $250$.

الإخراج

في السطر الأول، اطبع عدداً صحيحاً واحداً $q$ ($1 \le q \le 4000$) يمثل عدد الحالات في آلة DFA الخاصة بك.

في السطر $i$ من الأسطر الـ $q$ التالية، اطبع $n + 2$ أعداد صحيحة $\delta(i - 1, 0), \delta(i - 1, 1), \dots, \delta(i - 1, n + 1)$. يجب أن تكون جميعها بين $-(n + 1)$ و $q - 1$ شاملاً الطرفين وتتوافق مع انتقالات الآلة. لاحظ أن جميع الأعداد يجب أن تكون ضمن هذا النطاق: حتى لو كان من المستحيل الوصول إلى تركيبة معينة من الحالة $i$ ورقم الإدخال $j$ في أي إدخال صالح، فإن قيمة $\delta(i, j)$ التي تحددها يجب أن تظل ضمن النطاق $[-(n + 1), q - 1]$.

مثال

إدخال 1

4

إخراج 1

8
-3 0 0 1 0 0
2 1 1 1 1 1
-1 3 2 2 2 2
4 3 3 3 3 3
-5 4 4 4 4 5
6 5 5 5 5 5
-2 6 7 6 6 6
-4 7 7 7 7 7

ملاحظة

الإجابة الخاصة بالمثال هي آلة مملة للغاية تستخدم أربع تمريرات للتحقق مما إذا كانت المصفوفة تتضمن الأعداد 3 و 1 و 5 و 2 (بهذا الترتيب). تستخدم كل تمريرة فعلياً حالتين فقط تتوافقان مع ما إذا كانت قد وجدت بالفعل العدد الذي تبحث عنه في التمريرة الحالية. إذا وصلت إلى نهاية المصفوفة (الرمز 0) دون العثور على العدد المطلوب، فإنها تتوقف فوراً معلنة أن العدد المطلوب مفقود بالفعل. وإلا، فإنها تنتقل لاستخدام التمريرة التالية للبحث عن العدد التالي. أخيراً، إذا وجدت الأعداد الصحيحة الأربعة المطلوبة كلها، فلا بد أن العدد 4 مفقود. وبالتالي، لا تقوم بتمريرة خامسة للبحث عن العدد 4 (مع أنها كانت تستطيع فعل ذلك دون انتهاك القيود المفروضة على عدد حالات الآلة وعدد التمريرات المستخدمة).

بالطبع، هذا النهج الساذج لا يملك أي فرصة للنجاح عندما يكون $n = 250$، وهناك حاجة إلى طريقة أفضل بكثير. السبب الرئيسي لوجود المثال هو توضيح تنسيق الإخراج.

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1213EditorialOpen题解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.