Anna وBruno عالما آثار يدرسان أطلالًا في إيران.

تتوزع مهمتهما كما يلي: تزور Anna الأطلال وتكتشف القطع الأثرية، ويحلل Bruno النتائج في المعسكر الأساسي.

من المقرر أن يستمر بحثهما $Q(=1\,000)$ يوم. ترسل Anna النتائج إلى Bruno كل يوم باستخدام جهاز اتصال. تُمثَّل نتائج كل يوم بعدد صحيح $X$.

لا تستطيع Anna استخدام جهاز الاتصال إلا مرة واحدة في اليوم. يستطيع الجهاز إرسال متتالية طولها $N(=150)$ تتكون من $0$ و$1$.

لكن الجهاز معطل. توجد عدة مواضع معطلة في المتتالية ذات الطول $N$. يرسل كل موضع معطل القيمة $0$ دائمًا مهما كانت القيمة التي ضُبط عليها. عندما ترسل Anna متتالية، تستطيع معرفة مواقع المواضع المعطلة، لكن Bruno لا يعرفها. قد تتغير مواقع المواضع المعطلة وعددها كل يوم.

هناك خطر أن يتأخر بحثهما. ولأنك مرشح للمشاركة في مسابقة دولية للبرمجة في إيران، تطلب منك Anna وBruno كتابة برنامج يرسل نتائج بحثهما.

المهمة

اكتب برنامجين يحققان الاتصال بين Anna وBruno.

• يُعطى البرنامج الأول طول المتتالية $N$، والعدد الصحيح المراد إرساله $X$، وعدد المواضع المعطلة $K$، ومواقع المواضع المعطلة $P$، ويضبط المتتالية $S$ التي ترسلها Anna.
• يُعطى البرنامج الثاني المتتالية $A$ التي يستقبلها Bruno، ويستعيد العدد الصحيح $X$.

في كل موضع يعمل فيه جهاز الاتصال، تكون القيمة في المتتالية $S$ مساوية للقيمة في المتتالية $A$. أما في الموضع المعطل، فتكون القيمة في المتتالية $A$ دائمًا $0$ مهما كانت القيمة في المتتالية $S$.

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

عليك تسليم ملفين مكتوبين بلغة البرمجة نفسها.

الملف الأول هو Anna.c أو Anna.cpp. يضبط هذا الملف المتتالية التي ترسلها Anna، وينفذ الدالة التالية. يجب أن يتضمن البرنامج Annalib.h.

• void Anna( int N, long long X, int K, int P[] )

  تُستدعى هذه الدالة $Q=1\,000$ مرة لكل حالة اختبار.

  • المعامل N هو طول المتتالية المراد إرسالها.
  • المعامل X هو العدد الصحيح المراد إرساله.
  • المعامل K هو عدد المواضع المعطلة.
  • المعامل P[] هو متتالية طولها $K$ تصف مواقع المواضع المعطلة.

  يجب استدعاء الدالة التالية داخل الدالة Anna.

  • void Set( int pos, int bit )

    تضبط هذه الدالة بتًا في المتتالية $S$ التي سيرسلها جهاز الاتصال.

    • المعامل pos هو موقع الموضع المراد ضبطه. يجب أن يكون pos عددًا صحيحًا بين $0$ و$N-1$، شاملًا الطرفين. لاحظ أن ترقيم المواضع يبدأ من $0$. إذا استُدعيت الدالة بمعامل خارج هذا المجال، يُحكم على برنامجك بأنه إجابة خاطئة [1]. لا يُسمح باستدعاء هذه الدالة أكثر من مرة بالقيمة نفسها للمعامل pos. إذا استُدعيت أكثر من مرة بالمعامل نفسه، يُحكم على برنامجك بأنه إجابة خاطئة [2].
    • المعامل bit هو القيمة التي تُضبط في الموضع pos من المتتالية. يجب أن تكون قيمة bit إما $0$ أو $1$. إذا استُدعيت بقيمة أخرى، يُحكم على برنامجك بأنه إجابة خاطئة [3].

  يجب استدعاء الدالة Set بالضبط $N$ مرة داخل الدالة Anna. عند انتهاء الدالة Anna، إذا اختلف عدد استدعاءات Set عن $N$، يُحكم على برنامجك بأنه إجابة خاطئة [4].

  يُنهى برنامجك إذا اعتُبر استدعاء دالة من Anna غير صالح.

الملف الثاني هو Bruno.c أو Bruno.cpp. يستعيد هذا الملف العدد الصحيح الذي يمثل نتائج البحث، وينفذ الدالة التالية. يجب أن يتضمن البرنامج Brunolib.h.

• long long Bruno( int N, int A[] )

  تُستدعى هذه الدالة $Q=1\,000$ مرة لكل حالة اختبار.

  • المعامل N هو طول المتتالية التي يستقبلها Bruno.
  • المعامل A هو متتالية أعداد صحيحة طولها $N$، وهي المتتالية التي يستقبلها Bruno.
  • يجب أن تستعيد الدالة Bruno قيمة $X$ وتعيدها.

إجراءات التقييم

يُجرى التقييم بالطريقة التالية. إذا حُكم على برنامجك بأنه إجابة خاطئة، يُنهى فورًا.

1. اضبط $\mathrm{cnt}=0$.
2. استدعِ الدالة Anna مرة واحدة.
3. لتكن $S$ المتتالية التي ضبطتها الدالة Anna. في المتتالية $S$، اضبط القيمة $0$ في المواقع الموجودة في $P$ للحصول على المتتالية $A$. استدعِ الدالة Bruno مرة واحدة بالمعامل $A$.
4. اضبط $\mathrm{cnt}=\mathrm{cnt}+1$. إذا كان $\mathrm{cnt}<Q$، فانتقل إلى (2). وإذا كان $\mathrm{cnt}=Q$، فانتقل إلى (5).
5. تُحسب درجة برنامجك.

تنبيهات مهمة

• يُحسب زمن التشغيل واستخدام الذاكرة للخطوات (1) و(2) و(3) و(4) من إجراءات التقييم.
• يجب ألا يُحكم على برنامجك بأنه إجابة خاطئة عند استدعاء Anna في (2) أو Bruno في (3). ويجب أن يعمل برنامجك دون أخطاء وقت التشغيل.
• يمكن لبرنامجك تنفيذ دوال أخرى للاستخدام الداخلي أو استخدام متغيرات عامة. تُترجم البرامج المسلَّمة مع برنامج التقييم وتصبح ملفًا تنفيذيًا واحدًا. يجب تعريف جميع المتغيرات العامة والدوال الداخلية باستخدام static لتجنب التعارض مع الملفات الأخرى. ولأن برنامجي Anna وBruno سيعملان كعمليتين منفصلتين عند التقييم، فلا يمكنهما مشاركة المتغيرات العامة.
• خلال هذه العملية، تُستدعى كل من الدالتين Anna وBruno عدد $Q=1\,000$ مرة. يجب تهيئة المتغيرات المستخدمة في برنامجيك على نحو مناسب.
• يجب ألا يستخدم برنامجك الإدخال القياسي أو الإخراج القياسي. ويجب ألا يتواصل مع ملفات أخرى بأي وسيلة.

الترجمة والتشغيل التجريبي

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

يتكون برنامج التقييم التجريبي من ملف شيفرة مصدرية واحد، هو grader.c أو grader.cpp. مثلًا، إذا كان برنامجاك هما Anna.c وBruno.c، أو Anna.cpp وBruno.cpp، فنفذ الأوامر التالية لترجمتهما.

• C

  gcc -std=c11 -O2 -o grader grader.c Anna.c Bruno.c -lm

• C++

  g++ -std=c++14 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp

عند نجاح الترجمة، يُنشأ الملف التنفيذي grader.

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

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

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

• يحتوي السطر الأول على عدد صحيح $Q$.
• ثم تُعطى معلومات $Q$ استعلامات.

• تتكون معلومات كل استعلام من سطرين كما يلي.

  • يحتوي السطر الأول على ثلاثة أعداد صحيحة $N,X,K$ مفصولة بمسافات. وهذا يعني أن طول المتتالية المراد إرسالها هو $N$، والعدد الصحيح الذي تريد Anna إرساله هو $X$، وأن هناك $K$ مواضع معطلة.
  • يحتوي السطر الثاني على $K$ أعداد صحيحة $P_0,P_1,\ldots,P_{K-1}$ مفصولة بمسافات. وهذا يعني، لكل $i$ ($0 \le i \le K-1$)، أن الموضع $P_i$ من المتتالية معطل.

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

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

• إذا حُكم على برنامجك بأنه إجابة خاطئة، يكتب برنامج التقييم التجريبي نوعها بالشكل Wrong Answer [1]، ويُنهى برنامجك.
• إذا لم يُحكم على أي استدعاء للدالة Anna بأنه إجابة خاطئة، يكتب برنامج التقييم التجريبي Accepted وقيمة $L^*$. لمعرفة معنى $L^*$، انظر قسم المهام الفرعية.

إذا حُكم على برنامجك بأنه يتضمن عدة أنواع من الإجابة الخاطئة، فإن برنامج التقييم التجريبي لا يبلغ إلا عن نوع واحد منها.

القيود

تستوفي جميع بيانات الإدخال الشروط التالية.

• $Q=1000$.
• $N=150$.
• $0 \le X \le 1\,000\,000\,000\,000\,000\,000$.
• $1 \le K \le 40$.
• $0 \le P_i \le N-1$ ($0 \le i \le K-1$).
• $P_i<P_{i+1}$ ($0 \le i \le K-2$).

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

• لتكن $L^*$ أصغر قيمة للقيمة التالية عبر جميع حالات اختبار هذه المسألة.

  • أكبر عدد صحيح $L \le 40$ بحيث يعيد Bruno القيمة الصحيحة لـ$X$ في كل استعلام يحقق $K \le L$.

• تُحسب درجة هذه المسألة بالطريقة التالية:

  • إذا كان $L^*=0$، فالدرجة 0 نقطة.
  • إذا كان $1 \le L^* \le 14$، فالدرجة 8 نقاط.
  • إذا كان $15 \le L^* \le 37$، فالدرجة $(L^*-15)\times 2+41$ نقطة.
  • إذا كان $38 \le L^* \le 40$، فالدرجة $(L^*-38)\times 5+90$ نقطة.

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

فيما يلي مثال لإدخال برنامج التقييم واستدعاءات الدوال المقابلة. لاحظ أن المثال التالي لا يستوفي قيود هذه المسألة، لأن $Q=2$ و$N=3$.

الإدخال 1

2
3 14 1
2
3 9 2
0 1

استدعاءات الدوال

Anna(...)
    Set(0,0)
    Set(1,0)
    Set(2,1)
Bruno(...) -> 14
Anna(...)
    Set(0,0)
    Set(1,1)
    Set(2,1)
Bruno(...) -> 9

كل استدعاءات Set لا تعيد قيمة، وكذلك استدعاء Anna الأول المبيّن في الجدول الأصلي.

معاملات الاستدعاءات Anna(...) وBruno(...) وAnna(...) وBruno(...)، بالترتيب، هي كما يلي.