هذه مسألة تفاعلية.
خلفية المسألة
بعد مرور نصف عام، لم يعد I قادرًا على الاستمرار في تشغيل متجره. فقرر التنازل عنه وأن يصبح مستكشفًا يجوب العالم الواسع المجهول.
وفقًا لكتاب قديم، وجد في قلب صحراء شاسعة قصرًا تحت الأرض أنشأته حضارة مجهولة. يتكون القصر من $N$ كهفًا كبيرًا و$M$ ممرًا ثنائي الاتجاه تصل بينها. يستطيع I، بمساعدة الكتاب، تمييز الكهف الذي يوجد فيه، لكن الكتاب لا يوضح بنية اتصالات الممرات $M$، ولذلك يصعب عليه البحث عن الكنوز التي لا تنضب والتي تقول الأسطورة إنها مخبأة في القصر.
لكن I اكتشف الآن آلية غامضة يمكنه من خلالها الحصول على معلومات عن القصر. وقرر استخدامها لمعرفة بنية اتصالاته. ساعده في ذلك.
وصف المسألة
يمكن تمثيل القصر برسم بياني بسيط غير موجه له $N$ رأسًا و$M$ حافة. في الرسم البسيط، توجد حافة مباشرة واحدة على الأكثر بين أي رأسين. الكهوف مرقمة من $0$ إلى $n-1$، وأنت لا تعرف حاليًا ما الحواف الموجودة.
لكل كهف مصدر ضوء، له حالتان: التشغيل والإطفاء. لا يُضاء الكهف إلا إذا كان مصدر ضوئه مشغّلًا. في البداية تكون جميع مصادر الضوء مطفأة، ولا يمكن تغيير حالتها إلا بالآلية الغامضة التي اكتشفها I. وبالتحديد، يمكن استخدام الآلية لتنفيذ العمليات الأربع التالية:
- أعطِ الآلية رقمًا $x$، فتبدّل حالة مصدر الضوء في الكهف $x$ وفي جميع الكهوف المتصلة مباشرة به بممر: يتحول المشغّل إلى مطفأ والمطفأ إلى مشغّل.
- أعطِ الآلية رقمًا $x$، فتعرض الحالة الحالية لمصدر الضوء في الكهف $x$.
- أعطِ الآلية رقمين $x,y$، معلنًا أنك متأكد من وجود ممر بين الكهفين $x$ و$y$، لتسجله الآلية.
- أعطِ الآلية رقمًا $x$، فتحدد ما إذا كانت جميع الممرات المتصلة بالكهف $x$ قد سُجلت.
لا يمكن للآلية بدء عملية قبل إكمال العملية السابقة. كما لا يمكن استخدامها بلا حدود؛ فحدود عدد مرات تنفيذ العمليات الأربع هي، بالترتيب، $L_m,L_q,M,L_c$. مهمتك كتابة برنامج يساعد I على اختيار كيفية استخدام الآلية استخدامًا مناسبًا لاكتشاف الممرات $M$ كلها بصورة صحيحة.
تفاصيل التنفيذ
لست بحاجة إلى تنفيذ الدالة الرئيسية، ويجب ألا تنفذها. عليك تنفيذ الدالة explore(N, M) فقط، حيث يمثل $N$ عدد الكهوف و$M$ عدد الممرات. ويمكنك التفاعل مع مكتبة التفاعل باستدعاء الدوال الأربع التالية:
modify(x)
- تجعل هذه الدالة الآلية تنفذ العملية 1 بالرقم $x$.
- يجب ضمان $0\leq x<N$. لا تعيد هذه الدالة قيمة.
query(x)
- تجعل هذه الدالة الآلية تنفذ العملية 2 بالرقم $x$.
- يجب ضمان $0\leq x<N$. تعيد الدالة $0$ أو $1$، للدلالة على أن مصدر الضوء في الكهف $x$ مطفأ ($0$) أو مشغّل ($1$)، على الترتيب.
report(x, y)
- تجعل هذه الدالة الآلية تنفذ العملية 3 بالرقمين $x,y$.
- يجب ضمان $0\leq x,y<N$ و$x\ne y$. لا تعيد هذه الدالة قيمة.
check(x)
- تجعل هذه الدالة الآلية تنفذ العملية 4 بالرقم $x$.
- يجب ضمان $0\leq x<N$. تعيد الدالة $0$ أو $1$، وتعيد $1$ إذا وفقط إذا سُجلت جميع الممرات المتصلة بالكهف $x$ من خلال العملية 3.
أثناء التقييم، تستدعي مكتبة التفاعل الدالة explore مرة واحدة بالضبط.
يُضمن أن الرسم البياني المستخدم محدد بالكامل قبل بدء التفاعل، ولا يُبنى بصورة ديناميكية بحسب تفاعله مع برنامجك. لذلك فإن جميع العمليات التفاعلية في المسألة حتمية، ولست بحاجة إلى الاهتمام بتفاصيل تنفيذها داخل المكتبة.
يُضمن، ضمن حدود عدد الاستدعاءات، ألا يتجاوز زمن تشغيل مكتبة التفاعل ثانية واحدة. وحجم الذاكرة الذي تستخدمه المكتبة ثابت ولا يتجاوز $128$ ميغابايت.
طريقة التنفيذ
يتوفر الملف template_explore.cpp/c/pas في مجلد عمل المتسابق. انسخه وأعد تسمية النسخة إلى explore.cpp/c/pas، ثم اكتب حلك بالاعتماد عليها.
لمستخدمي C++ وC
- تأكد من وجود
#include "explore.h"في بداية برنامجك. - واجهة الدالة
exploreالتي عليك تنفيذها هي:
void explore(int N, int M);
- واجهات دوال التفاعل التي يمكنك استدعاؤها هي:
void modify(int x); int query(int x); void report(int x, int y); int check(int x);
لمستخدمي Pascal
- انتبه: صياغة تنفيذ الواجهات في Pascal معقدة نسبيًا. لذلك اكتب حلك مباشرة بالاعتماد على الملف الموزع
template_explore.pas، بدلًا من كتابة البرنامج من الصفر. - واجهة الدالة
exploreالتي عليك تنفيذها هي:
procedure _explore(N, M : longint);
- انتبه إلى أن اسم الدالة هنا
_exploreوليسexplore؛ واستخدام الاسمexploreيؤدي إلى فشل الترجمة. - واجهات دوال التفاعل التي يمكنك استدعاؤها هي:
procedure modify(x : longint); function query(x : longint) : longint; procedure report(x : longint; y : longint); function check(x : longint) : longint;
كيفية اختبار البرنامج
الملفان grader.cpp/c وgraderhelperlib.pas في مجلد المسألة هما تنفيذ مرجعي لمكتبة التفاعل نوفره لكم. يختلف تنفيذ المكتبة في الاختبارات النهائية عن هذا التنفيذ المرجعي، ولذلك يجب ألا يعتمد حلك على تفاصيل تنفيذ المكتبة.
لمستخدمي C وC++
استخدم الأوامر التالية في مجلد المسألة لترجمة البرنامج إلى ملف تنفيذي.
للغة C:
gcc grader.c explore.c -o explore -O2 -lm
للغة C++:
g++ grader.cpp explore.cpp -o explore -O2 -lm
لمستخدمي Pascal
استخدم الأمر التالي في مجلد المسألة لترجمة البرنامج إلى ملف تنفيذي:
fpc grader.pas -o"explore" -O2
تشغيل الملف التنفيذي
يقرأ الملف التنفيذي من الإدخال القياسي بيانات بالصيغة التالية:
يحتوي السطر الأول على الأعداد الصحيحة الثلاثة $L_m,L_q,L_c$، ويحتوي السطر الثاني على العددين الصحيحين $N,M$، بمعانيها الواردة في وصف المسألة.
تحتوي الأسطر $M$ التالية، كل منها، على عددين صحيحين $x,y$، يصفان ممرًا بين الكهفين $x$ و$y$.
بعد اكتمال القراءة، تستدعي مكتبة التفاعل الدالة explore مرة واحدة بالضبط، وتختبرها باستخدام بيانات الإدخال. عندما تعود دالتك بصورة طبيعية، تتحقق المكتبة من صحة حساباتك. إذا كانت صحيحة، تطبع Correct ومعلومات عن عدد استدعاءات دوال التفاعل؛ وإلا تطبع رسالة الخطأ المناسبة.
أمثلة
افترض أن البيانات التي يقرؤها الملف التنفيذي هي:
الإدخال 1
100 200 300 3 2 0 1 1 2
تمثل الأعداد الثلاثة في السطر الأول حدود عدد استدعاءات ثلاث عمليات: لا يجوز استدعاء modify(x) أكثر من $100$ مرة، ولا query(x) أكثر من $200$ مرة، ولا check(x) أكثر من $300$ مرة.
يمثل العددان في السطر الثاني عدد الكهوف وعدد الممرات، أي $N=3$ و$M=2$.
لا يجوز أن يتجاوز عدد استدعاءات report(x, y) القيمة $M$، أي مرتين في هذا المثال.
فيما يلي تفاعل صحيح:
| برنامج المتسابق | مكتبة التفاعل | التوضيح |
|---|---|---|
تستدعي explore(3, 2) |
بدء الاختبار | |
يستدعي modify(0) |
تنفيذ العملية 1 على الكهف $0$ | |
يستدعي query(2) |
تعيد $0$ | مصدر الضوء في الكهف $2$ مطفأ حاليًا |
يستدعي report(0, 1) |
اكتشاف الممر $(0,1)$ وتسجيله | |
يستدعي check(0) |
تعيد $1$ | سُجلت جميع الممرات المتصلة بالكهف $0$ |
يستدعي report(2, 1) |
اكتشاف الممر $(2,1)$ وتسجيله | |
| ينتهي التنفيذ ويعود | تطبع Correct على الشاشة |
انتهاء التفاعل، والنتيجة صحيحة |
شرح الملفات الموزعة
في مجلد هذه المسألة:
grader.cpp/cوgraderhelperlib.pasهما التنفيذ المرجعي لمكتبة التفاعل الذي نوفره.explore.hوgrader.pasملفا ترويسة، ولا حاجة إلى الاهتمام بمحتواهما التفصيلي.template_explore.cpp/c/pasهو ملف مصدر الحل النموذجي الذي نوفره.explore1.inوexplore2.inوexplore3.inملفات إدخال أمثلة يمكن استخدامها للاختبار.
احرص على إنشاء نسخة احتياطية من جميع الملفات الموزعة. لا يجمع نظام التقييم إلا الملف explore.c/cpp/pas من مجلد المسألة، ولا يكون لتعديل الملفات الأخرى أي أثر.
المهام الفرعية
لا يجمع التقييم النهائي إلا الملف explore.cpp/c/pas؛ ولا يكون لتعديل الملفات الأخرى في مجلد المتسابق أي أثر على التقييم.
تخضع هذه المسألة أولًا للقيود نفسها التي تخضع لها المسائل التقليدية. فمثلًا، يؤدي خطأ الترجمة إلى صفر في المسألة كلها، وتؤدي أخطاء التشغيل وتجاوز حد الزمن أو الذاكرة إلى صفر في نقطة الاختبار المقابلة. لا يجوز لك الوصول إلا إلى المتغيرات التي تعرّفها والمتغيرات التي توفرها مكتبة التفاعل ومساحات الذاكرة المقابلة لها. وقد تؤدي محاولة الوصول إلى مساحات أخرى إلى خطأ ترجمة أو تشغيل.
بالإضافة إلى الشروط السابقة، تحصل على النقاط كاملة في نقطة اختبار إذا وفقط إذا:
- كان كل استدعاء للدوال صالحًا، ولم تتجاوز أعداد استدعاءات
modifyوqueryوcheckالحدود $L_m,L_q,L_c$، على الترتيب. - بما أن حد استدعاءات
reportهو $M$، وجب أن يسجل كل استدعاء حافة موجودة وجديدة. أي إنه عند كل استدعاءreport(x, y)، يجب وجود ممر بين الكهفين $x$ و$y$، وألا يكون قد سبق استدعاءreport(x, y)ولاreport(y, x). - عادت دالتك
exploreبصورة طبيعية. - عند عودة
explore، كنت قد سجلت الممرات $M$ كلها باستدعاءاتreport.
القيود
توجد $25$ نقطة اختبار، قيمة كل منها $4$ نقاط. يبين الجدول التالي أحجام البيانات والحدود المقابلة لكل نقطة:
| رقم نقطة الاختبار | $N=$ | $M=$ | $L_m=$ | $L_q=$ | $L_c=$ | الخاصية الخاصة |
|---|---|---|---|---|---|---|
| $1$ | $3$ | $2$ | $100$ | $100$ | $100$ | لا توجد |
| $2$ | $100$ | $10N$ | $200$ | $10^4$ | $2M$ | لا توجد |
| $3$ | $200$ | $10N$ | $200$ | $4\times10^4$ | $2M$ | لا توجد |
| $4$ | $300$ | $10N$ | $299$ | $9\times10^4$ | $2M$ | لا توجد |
| $5$ | $500$ | $10N$ | $499$ | $1.5\times10^5$ | $2M$ | لا توجد |
| $6$ | $59998$ | $N/2$ | $17N$ | $17N$ | $0$ | A |
| $7$ | $99998$ | $N/2$ | $18N$ | $18N$ | $0$ | A |
| $8$ | $199998$ | $N/2$ | $19N$ | $19N$ | $0$ | A |
| $9$ | $199998$ | $N/2$ | $19N$ | $19N$ | $0$ | A |
| $10$ | $99997$ | $N-1$ | $18N$ | $18N$ | $0$ | B |
| $11$ | $199997$ | $N-1$ | $19N$ | $19N$ | $0$ | B |
| $12$ | $99996$ | $N-1$ | $10^7$ | $10^7$ | $2M$ | C |
| $13$ | $199996$ | $N-1$ | $10^7$ | $10^7$ | $2M$ | C |
| $14$ | $199996$ | $N-1$ | $10^7$ | $10^7$ | $2M$ | C |
| $15$ | $99995$ | $N-1$ | $10^7$ | $10^7$ | $2M$ | D |
| $16$ | $99995$ | $N-1$ | $10^7$ | $10^7$ | $2M$ | D |
| $17$ | $199995$ | $N-1$ | $10^7$ | $10^7$ | $2M$ | D |
| $18$ | $1004$ | $2000$ | $10^7$ | $5\times10^4$ | $2M$ | لا توجد |
| $19$ | $1004$ | $3000$ | $10^7$ | $5\times10^4$ | $2M$ | لا توجد |
| $20$ | $1004$ | $3000$ | $10^7$ | $5\times10^4$ | $2M$ | لا توجد |
| $21$ | $50000$ | $2N$ | $10^7$ | $10^7$ | $2M$ | لا توجد |
| $22$ | $100000$ | $2N$ | $10^7$ | $10^7$ | $2M$ | لا توجد |
| $23$ | $150000$ | $200000$ | $10^7$ | $10^7$ | $2M$ | لا توجد |
| $24$ | $200000$ | $250000$ | $10^7$ | $10^7$ | $2M$ | لا توجد |
| $25$ | $200000$ | $300000$ | $10^7$ | $10^7$ | $2M$ | لا توجد |
نذكّر مجددًا بأن الرسم البياني المستخدم في الاختبار محدد بالكامل قبل بدء التفاعل، ولا يُبنى بصورة ديناميكية بحسب تفاعله مع برنامجك.
معاني الخصائص الخاصة في الجدول هي:
A: درجة كل رأس تساوي $1$ بالضبط.
B: لكل $x>0$، يوجد عدد واحد بالضبط $y<x$ بحيث يوجد ممر مباشر بين الكهفين $x$ و$y$.
C: يوجد تبديل $p_0,p_1,\ldots,p_{N-1}$ للأعداد من $0$ إلى $N-1$، بحيث يوجد لكل $1\leq i<N$ ممر بين الكهفين $p_{i-1}$ و$p_i$.
D: الرسم البياني متصل.
- تلميح: يمكن لبرنامجك التمييز بين أنواع البيانات السابقة بالنظر إلى رقم الآحاد في قيمة $N$ الممررة إليه.