هل تعرف شركة Just Ordinary Inventions؟ عمل هذه الشركة هو تقديم «اختراعات عادية فحسب».

يلعب JOI أحدث لعبة طورتها شركة Just Ordinary Inventions.

في هذه اللعبة، تستكشف دهليزاً يتكون من عدة غرف وطرق. تصل كل طريق بين غرفتين مختلفتين في الدهليز، ويمكن اجتيازها في كلا الاتجاهين. لا توجد أكثر من طريق واحدة بين أي غرفتين مختلفتين، ولا توجد طريق ينتمي طرفاها إلى الغرفة نفسها. ومن المعروف أيضاً أنه يمكن الانتقال بين أي غرفتين في الدهليز باستخدام عدد من الطرق. تتشابه الغرف كثيراً، ولا يمكن إطلاقاً التمييز بين غرفتين يخرج منهما العدد نفسه من الطرق بمجرد النظر إليهما.

لمساعدة اللاعب، توجد في كل غرفة علامة مرجعية وقاعدة. يمكن عد الطرق الخارجة من الغرفة بالنسبة إلى العلامة: الطريق الأولى، الثانية، وهكذا. لا تتغير بنية الدهليز أثناء اللعبة. لذا فإن استخدام الطريق ذات الرقم نفسه من الغرفة نفسها يؤدي دائماً إلى الغرفة نفسها. وعلى القاعدة جوهرة واحدة يستطيع اللاعب تغيير لونها. يكون لون الجوهرة أحد الألوان $1,2,\ldots,X$، وعند بدء اللعبة يكون لون الجوهرة في كل غرفة هو اللون $1$. ولا يتغير لون أي جوهرة إلا إذا غيّره اللاعب.

لاحظ JOI أن اللعبة ستصبح سهلة إذا عرف بنية الدهليز، أي كيفية اتصال غرفه بالطرق. لكنه لم يتمكن من تحديد البنية رغم تجاربه المختلفة. لذلك قررت كتابة برنامج يحدد بنية الدهليز نيابة عنه.

المهمة

اكتب برنامجاً يستكشف الدهليز ويحدد بنيته. لكن JOI لا يريد أن تنكشف له البنية كاملة، لذا يجب على البرنامج، بدلاً من وصفها مباشرة، أن يجيب لكل عدد صحيح $i$ بين $1$ و$R$ عن السؤال: «كم عدد أزواج الغرف التي يتطلب الانتقال بينها، في أقصر مسار، $i$ طرق بالضبط؟» ويُعد تبديل ترتيب الغرفتين الزوج نفسه.

لاستكشاف الدهليز، تُعطى مكتبة تتيح لك تنفيذ الأفعال الآتية:

• معرفة عدد الطرق الخارجة من الغرفة الحالية.
• معرفة لون الجوهرة المعروضة على قاعدة الغرفة الحالية.
• تغيير لون الجوهرة المعروضة على قاعدة الغرفة الحالية إلى لون محدد (يمكن تحديد لونها الحالي نفسه)، ثم اختيار إحدى الطرق الخارجة من الغرفة والانتقال عبرها إلى غرفة أخرى.
• معرفة رقم آخر طريق استخدمتها ضمن الطرق الخارجة من الغرفة الحالية.

تفاصيل التنفيذ

يجب أن تكتب برنامجاً واحداً ينفذ طريقة الإجابة عن أسئلة JOI. يجب أن يضمّن البرنامج dungeon2.h.

يجب أن ينفذ البرنامج الروتين الآتي.

• void Inspect(int R)

  يُستدعى هذا الروتين مرة واحدة فقط في البداية.

  • يعني المعامل R أنه يجب عليك الإجابة، لكل عدد صحيح $i$ بين $1$ و$R$، عن عدد أزواج الغرف التي يتطلب أقصر مسار بينها $i$ طرق بالضبط (ويُعد تبديل ترتيب الغرفتين الزوج نفسه).

ويجب عليك استدعاء الروتين الآتي للإجابة عن الأسئلة.

• void Answer(int D, int A)

  • يعني المعاملان D وA أنك تجيب في هذا الاستدعاء بأن عدد أزواج الغرف التي يتطلب أقصر مسار بينها $D$ طرق بالضبط هو $A$.

يجب أن تستوفي استدعاءات Answer الشروط الآتية.

• يجب أن يكون D عدداً صحيحاً بين $1$ و$R$، وإلا تكون النتيجة إجابة خاطئة [1].
• يجب ألا تستدعي Answer مرتين أو أكثر بالقيمة نفسها للمعامل D، وإلا تكون النتيجة إجابة خاطئة [2].
• يجب استدعاء Answer بالضبط $R$ مرة، وإلا تكون النتيجة إجابة خاطئة [3].
• يجب أن يكون A هو عدد أزواج الغرف التي يتطلب أقصر مسار بينها $D$ طرق بالضبط، وإلا تكون النتيجة إجابة خاطئة [4].

إذا حُكم بأن استدعاء Answer خاطئ، فليس مضموناً أن يستمر تنفيذ البرنامج بعد ذلك.

بالإضافة إلى ذلك، يمكنك استدعاء الروتينات الآتية في برنامجك.

• void Move(int I, int C)

  • المعامل I هو رقم الطريق التي يختارها اللاعب للانتقال. بعد هذا الاستدعاء مباشرة، ينتقل اللاعب إلى غرفة أخرى عبر الطريق رقم $I$ الخارجة من الغرفة الحالية.
  • يعني المعامل C أن لون الجوهرة المعروضة على قاعدة الغرفة الحالية يصبح اللون $C$ قبل الانتقال إلى الغرفة الأخرى.

يجب أن تستوفي استدعاءات Move الشروط الآتية.

• إذا كان عدد الطرق الخارجة من الغرفة الحالية هو $K$، فيجب أن يكون المعامل I عدداً صحيحاً بين $1$ و$K$، وإلا تكون النتيجة إجابة خاطئة [5].
• إذا كان عدد ألوان الجواهر هو $X$، فيجب أن يكون المعامل C عدداً صحيحاً بين $1$ و$X$. تُحدَّد قيمة $X$ لكل مهمة فرعية. إذا لم يتحقق هذا الشرط، تكون النتيجة إجابة خاطئة [6].

• يجب ألا يتجاوز عدد استدعاءات Move مقدار $1\,500\,000$، وإلا تكون النتيجة إجابة خاطئة [7].

• int NumberOfRoads()

  • تعيد هذه الدالة عدد الطرق الخارجة من الغرفة الحالية للاعب.

• int LastRoad()

  • تعيد هذه الدالة رقم آخر طريق استخدمها اللاعب ضمن الطرق الخارجة من الغرفة الحالية. لكن إذا استُدعيت قبل استدعاء Move ولو مرة واحدة، فإنها تعيد $-1$.

• int Color()

  • تعيد هذه الدالة لون الجوهرة المعروضة على قاعدة الغرفة الحالية للاعب.

بعد استدعاء الروتين Inspect، تُفحص الإجابات.

يمكنك تنفيذ روتينات أخرى للاستخدام الداخلي أو التصريح بمتغيرات عامة بحرية. لكن يجب ألا يتبادل برنامجك أي بيانات، بأي وسيلة، مع الإدخال القياسي أو الإخراج القياسي أو أي ملفات أخرى.

طريقة الترجمة والتنفيذ

يتضمن الأرشيف القابل للتنزيل من موقع المسابقة نموذجاً لبرنامج التقييم لاختبار برنامجك. ويتضمن الأرشيف أيضاً نموذجاً للملف الذي يجب تسليمه.

يتكون نموذج برنامج التقييم من ملف واحد، هو grader.c أو grader.cpp. لاختبار برنامجك، نفّذ الأوامر كما يأتي.

• عند استخدام C

  gcc -std=c11 -O2 -o grader grader.c dungeon2.c -lm

• عند استخدام C++

  g++ -std=c++11 -O2 -o grader grader.cpp dungeon2.cpp

إذا نجحت الترجمة، يُنشأ ملف تنفيذي اسمه grader.

لاحظ أن برنامج التقييم الفعلي يختلف عن النموذج. يعمل النموذج بوصفه عملية واحدة، ويقرأ البيانات من الإدخال القياسي ويكتب النتائج في الإخراج القياسي.

إدخال نموذج برنامج التقييم

يقرأ النموذج البيانات الآتية من الإدخال القياسي.

• يحتوي السطر الأول على الأعداد الصحيحة $N,X,R$ مفصولة بمسافات. وهذا يعني وجود $N$ غرفة في الدهليز، هي الغرف $1,2,\ldots,N$، ووجود $X$ ألوان للجواهر، وأن عدد القيم التي يجب على البرنامج الإجابة عنها هو $R$.
• في الأسطر $2N$ التالية، يحتوي السطر $2i-1$ ($1 \le i \le N$) على عدد صحيح $D_i$، ويعني أن عدد الطرق الخارجة من الغرفة $i$ هو $D_i$. ويحتوي السطر $2i$ ($1 \le i \le N$) على $D_i$ عدداً صحيحاً $T_{i1},T_{i2},\ldots,T_{iD_i}$ مفصولة بمسافات. وهذا يعني أن استخدام الطريق رقم $j$ ($1 \le j \le D_i$) الخارجة من الغرفة $i$ يؤدي إلى الغرفة $T_{ij}$.
• يحتوي السطر $j$ ($1 \le j \le R$) من الأسطر $R$ التالية على عدد صحيح $A_j$، ويعني أن عدد أزواج الغرف التي يتطلب أقصر مسار بينها $j$ طرق بالضبط هو $A_j$. أي إنه، لكل $j$ ($1 \le j \le R$)، يحكم النموذج بصحة استدعاء Answer إذا أُعطيت القيمة $j$ للمعامل D والقيمة $A_j$ للمعامل A، ويحكم بخطئه فيما عدا ذلك.

يستدعي النموذج الروتين الذي كتبته، ويكون موضع اللاعب الابتدائي هو الغرفة $1$.

إخراج نموذج برنامج التقييم

إذا انتهى تنفيذ البرنامج بصورة طبيعية، يكتب النموذج المعلومات الآتية في سطر واحد في الإخراج القياسي (لا تُطبع علامتا الاقتباس فعلياً).

• إذا كانت الإجابة صحيحة، يُطبع عدد استدعاءات Move بصيغة مثل Accepted : #move = 8.
• إذا كانت الإجابة خاطئة، يُطبع نوع الخطأ بصيغة مثل Wrong Answer [1].

القيود

تستوفي جميع بيانات الإدخال الشروط الآتية. لمعاني $N,D_i,T_{ij}$، راجع قسم «إدخال نموذج برنامج التقييم».

• $2 \le N \le 200$.
• $3 \le X \le 100$.
• $1 \le R \le 200$.
• $1 \le D_i \le N-1$ ($1 \le i \le N$).
• $1 \le T_{ij} \le N$ و$T_{ij} \ne i$ ($1 \le i \le N$، $1 \le j \le D_i$).
• القيم $T_{i1},T_{i2},\ldots,T_{iD_i}$ ($1 \le i \le N$) مختلفة عن بعضها.
• لكل $i,j$ ($1 \le i \le N$، $1 \le j \le D_i$)، يوجد $k$ ($1 \le k \le D_{T_{ij}}$) يحقق $T_{T_{ij}k}=i$.
• يمكن الانتقال بين أي غرفتين باستخدام عدد من الطرق.

المهام الفرعية

فيما يأتي، نرمز إلى عدد غرف الدهليز في بيانات الإدخال بـ$N$ وإلى عدد الطرق بـ$M$.

المهمة الفرعية 1 [17 نقطة]

تتحقق الشروط الآتية.

• $N \le 50$.
• $M \le 100$.
• $X=100$.

المهمة الفرعية 2 [27 نقطة]

تتحقق الشروط الآتية.

• $N \le 50$.
• $M \le 100$.
• $X=3$.

المهمة الفرعية 3 [56 نقطة]

• $X=3$.

تُحدَّد نقاط هذه المهمة الفرعية كما يأتي.

• ليكن $L$ أكبر قيمة للمقدار الآتي بين جميع حالات اختبار هذه المهمة الفرعية.

  • $\dfrac{C}{M}$، حيث $C$ هو عدد استدعاءات Move.

• عندئذ تكون نقاط هذه المهمة الفرعية:

  • $56$ نقطة إذا كان $L \le 14$.
  • $\lfloor 70-L \rfloor$ نقطة إذا كان $14 < L \le 32$.
  • $\left\lfloor 54-\dfrac{L}{2}\right\rfloor$ نقطة إذا كان $32 < L \le 64$.
  • $0$ نقطة إذا كان $64 < L$.

هنا، يرمز $\lfloor x \rfloor$ إلى أكبر عدد صحيح لا يتجاوز $x$.

في نظام التقييم، إذا انتهى البرنامج بصورة صحيحة وحُكم بصحة الإجابة، تظهر Accepted في خانة التفاصيل. لكن انتبه إلى أنه في تقييم المهمة الفرعية $3$، تظهر إجابة خاطئة في خانة النتيجة لحالات الاختبار التي يحقق فيها $C,M$ أعلاه الشرط $64 < \dfrac{C}{M}$.

مثال على التفاعل

فيما يأتي مثال على الإدخال الذي يقرأه نموذج برنامج التقييم، ومثال على استدعاءات الروتينات الموافقة له.

الإدخال 1

4 3 3
1
2
3
1 3 4
2
2 4
2
2 3
4
2
0

مثال على استدعاءات الروتينات

لاحظ أن استدعاءات الدوال في هذا المثال ليست بالضرورة استدعاءات ذات معنى.