Anna وBruno محترفان في ألعاب المقامرة. سيلعبان لعبة مع D-taro، الذي يدير اللعبة.
في هذه اللعبة، يبقى Anna وBruno في غرفتين مختلفتين، ولا يمكنهما التواصل إلا باستخدام جهاز معطل. يعطي D-taro عددًا صحيحًا إلى Anna. وهدف Anna وBruno في اللعبة هو نقل العدد المعطى من Anna إلى Bruno باستخدام الجهاز.
في بداية اللعبة، تعلن Anna عددًا صحيحًا $m$ بين $1$ و$2\,000$، شاملًا الطرفين. ثم يلعبان $Q$ جولات. تجري الجولة $i$ ($1\le i\le Q$) كما يلي.
- يعطي D-taro عددًا صحيحًا $A_i$ إلى Anna.
- تدخل Anna المصفوفتين $s_i,t_i$ في الجهاز. يجب أن يكون كل عنصر فيهما إما $0$ أو $1$. ويجب أن تتساويا في الطول، وأن يكون الطول بين $1$ و$m$، شاملًا الطرفين.
- لتكن $u_i$ مصفوفة ناتجة من المصفوفتين $s_i,t_i$ بعملية الخلط التداخلي (الموضحة أدناه). يرسل الجهاز $u_i$ إلى Bruno.
- يرسل Bruno عددًا صحيحًا إلى D-taro. إذا ساوى هذا العدد العدد $A_i$ الذي أعطاه D-taro إلى Anna، يفوز Anna وBruno في هذه الجولة.
اكتب برنامجين ينفذان استراتيجيتي Anna وBruno بحيث يفوزان في جميع الجولات $Q$.
الخلط التداخلي
نقول إن المصفوفة $Z$ ناتجة من المصفوفتين $X,Y$ بعملية الخلط التداخلي إذا أمكن تقسيم عناصر $Z$ إلى مجموعتين تحققان الشرطين التاليين.
- المصفوفة المكونة من عناصر المجموعة الأولى، بالترتيب نفسه، تساوي المصفوفة $X$.
- المصفوفة المكونة من عناصر المجموعة الثانية، بالترتيب نفسه، تساوي المصفوفة $Y$.
مثلًا، تنتج المصفوفة $Z=[1,1,1,0,0,0]$ من $X=[1,1,0]$ و$Y=[1,0,0]$ بعملية الخلط التداخلي، لأن المصفوفة المكونة من العناصر الأول والثاني والرابع في $Z$، بالترتيب نفسه، هي $[1,1,0]$، والمصفوفة المكونة من العناصر الثالث والخامس والسادس، بالترتيب نفسه، هي $[1,0,0]$.
أما إذا كانت $X=[1,1,0]$ و$Y=[1,0,0]$ و$Z=[0,0,0,1,1,1]$، فلا تنتج $Z$ من $X,Y$ بعملية الخلط التداخلي.
تفاصيل التنفيذ
يجب أن تسلم ملفين.
الملف الأول هو Anna.cpp، ويجب أن ينفذ استراتيجية Anna من خلال الدوال التالية. يجب أن يضم البرنامج الملف Anna.h باستخدام توجيه المعالج المسبق #include.
int Declare()تستدعى هذه الدالة مرة واحدة في البداية.
- القيمة المعادة هي العدد الصحيح $m$ الذي تعلنه Anna.
- يجب أن يكون $m$ بين $1$ و$2\,000$، شاملًا الطرفين. وإلا يحكم على برنامجك بالنتيجة Wrong Answer [1].
std::pair<std::vector<int>, std::vector<int> > Anna(long long A)بعد استدعاء
Declare، تستدعى هذه الدالة $Q$ مرات. يقابل الاستدعاء $i$ ($1\le i\le Q$) الخطوتين 1 و2 من الجولة $i$.- الوسيط
Aهو العدد الصحيح $A_i$ الذي يعطيه D-taro إلى Anna. - القيمة المعادة هي زوج المصفوفتين $s_i,t_i$ اللتين تدخلهما Anna في الجهاز.
- يجب أن يكون كل عنصر في $s_i,t_i$ إما $0$ أو $1$. وإلا يحكم على برنامجك بالنتيجة Wrong Answer [2].
- يجب أن يكون طول كل من $s_i,t_i$ بين $1$ و$m$، شاملًا الطرفين. وإلا يحكم على برنامجك بالنتيجة Wrong Answer [3].
- يجب أن تتساوى المصفوفتان $s_i,t_i$ في الطول. وإلا يحكم على برنامجك بالنتيجة Wrong Answer [4].
- الوسيط
الملف الثاني هو Bruno.cpp، ويجب أن ينفذ استراتيجية Bruno من خلال الدالة التالية. يجب أن يضم البرنامج الملف Bruno.h باستخدام توجيه المعالج المسبق #include.
long long Bruno(std::vector<int> u)بعد أن تدخل Anna المصفوفتين في الجهاز، تستدعى هذه الدالة مرة واحدة. وتستدعى في المجموع $Q$ مرات. يقابل الاستدعاء $i$ ($1\le i\le Q$) الخطوتين 3 و4 من الجولة $i$.
- الوسيط
uهو المصفوفة $u_i$ التي يرسلها الجهاز إلى Bruno في الجولة $i$. - القيمة المعادة هي العدد الصحيح الذي يرسله Bruno إلى D-taro.
- يجب أن تساوي القيمة المعادة العدد $A_i$ الذي أعطاه D-taro إلى Anna. وإلا يحكم على برنامجك بالنتيجة Wrong Answer [5].
- الوسيط
ملاحظات مهمة
- يمكن لبرنامجك تنفيذ دوال أخرى للاستخدام الداخلي أو استخدام متغيرات عامة. ستترجم الملفات المسلمة مع برنامج التقييم لتصبح ملفًا تنفيذيًا واحدًا. يجب تعريف جميع المتغيرات العامة والدوال الداخلية في نطاق أسماء غير مسمى لتجنب التعارض مع الملفات الأخرى. أثناء التقييم، ينفذ البرنامج في عمليتين منفصلتين لـAnna وBruno، ولا يمكنهما مشاركة المتغيرات العامة.
- يجب ألا يستخدم برنامجك الإدخال القياسي أو الإخراج القياسي، وألا يتواصل مع ملفات أخرى بأي وسيلة. لكن يسمح له بإخراج معلومات تصحيح الأخطاء إلى مجرى الخطأ القياسي.
الترجمة والتشغيل التجريبي
يمكنك تنزيل أرشيف من صفحة المسابقة يحتوي على برنامج تقييم نموذجي لاختبار برنامجك. ويحتوي الأرشيف أيضًا على ملف مصدر نموذجي لبرنامجك.
برنامج التقييم النموذجي هو الملف grader.cpp. لاختبار برنامجك، ضع الملفات grader.cpp وAnna.cpp وBruno.cpp وAnna.h وBruno.h في المجلد نفسه، ثم نفذ الأمر التالي لترجمة برامجك.
g++ -std=gnu++17 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp
عند نجاح الترجمة، ينشأ الملف التنفيذي grader.
لاحظ أن برنامج التقييم الفعلي يختلف عن النموذجي. ينفذ برنامج التقييم النموذجي في عملية واحدة، ويقرأ بيانات الإدخال من الإدخال القياسي ويكتب النتائج إلى الإخراج القياسي.
الإدخال لبرنامج التقييم النموذجي
يقرأ برنامج التقييم النموذجي البيانات التالية من الإدخال القياسي.
$$ \begin{gathered} Q\\ A_1\\ A_2\\ \vdots\\ A_Q \end{gathered} $$
الإخراج من برنامج التقييم النموذجي
يخرج برنامج التقييم النموذجي المعلومات التالية إلى الإخراج القياسي (علامات التنصيص للتوضيح).
- إذا حكم على برنامجك بأنه صحيح، يكتب القيمة $m$ المعادة من
DeclareبالشكلAccepted: 2000. - إذا حكم على برنامجك بأي نوع من أنواع Wrong Answer، يكتب برنامج التقييم النموذجي نوعه بالشكل
Wrong Answer [1].
إذا حقق برنامجك شروط عدة أنواع من Wrong Answer، يبلغ برنامج التقييم النموذجي عن نوع واحد فقط.
عند تشغيل برنامج التقييم النموذجي، تحسب عملية الخلط التداخلي لكل جولة باستخدام أعداد شبه عشوائية. لا تتغير النتائج بين مرات التشغيل. لتغيير بذرة الأعداد شبه العشوائية، شغل برنامج التقييم النموذجي بالطريقة التالية.
./grader 2022
يجب أن يكون الوسيط الأول عددًا صحيحًا.
القيود
- $1\le Q\le 1\,000$.
- $1\le A_i\le 1\,000\,000\,000\,000\,000\,000\ (=10^{18})$ ($1\le i\le Q$).
المهام الفرعية
- (5 نقاط) $A_i\le 2\,000$ ($1\le i\le Q$).
- (5 نقاط) $A_i\le 4\,000\,000$ ($1\le i\le Q$).
- (3 نقاط) $A_i\le 10\,000\,000\ (=10^7)$ ($1\le i\le Q$).
- (12 نقطة) $A_i\le 100\,000\,000\ (=10^8)$ ($1\le i\le Q$).
- (15 نقطة) $A_i\le 100\,000\,000\,000\ (=10^{11})$ ($1\le i\le Q$).
(60 نقطة) لا توجد قيود إضافية. تحسب درجتك في هذه المهمة الفرعية كما يلي.
- لتكن $m^*$ أكبر قيمة بين الأعداد الصحيحة $m$ التي تعلنها Anna في جميع حالات الاختبار لهذه المهمة الفرعية.
- تكون درجتك كما يلي.
| قيمة $m^*$ | الدرجة |
|---|---|
| $201\le m^*\le 2\,000$ | $40-25\times\log_{10}\left(\frac{m^*}{200}\right)$ نقطة (مع التقريب إلى الأسفل لأقرب عدد صحيح) |
| $161\le m^*\le 200$ | 40 نقطة |
| $156\le m^*\le 160$ | 44 نقطة |
| $151\le m^*\le 155$ | 48 نقطة |
| $146\le m^*\le 150$ | 52 نقطة |
| $141\le m^*\le 145$ | 56 نقطة |
| $m^*\le 140$ | 60 نقطة |
أمثلة
فيما يلي إدخال نموذجي لبرنامج التقييم النموذجي واستدعاءات الدوال المقابلة له.
الإدخال 1
2 42 2000
استدعاءات الدوال النموذجية
| الاستدعاء | القيمة المعادة |
|---|---|
Declare() |
4 |
Anna(42) |
([0, 0, 1, 0], [1, 1, 0, 1]) |
Bruno([1, 0, 0, 1, 0, 1, 0, 1]) |
42 |
Anna(2000) |
([0, 1], [0, 0]) |
Bruno([0, 0, 1, 0]) |
2000 |
ملاحظة
في هذا الإدخال النموذجي، توجد $Q\ (=2)$ جولتان. في الجولة الأولى، يعطي D-taro العدد الصحيح $A_1\ (=42)$ إلى Anna. وفي الجولة الثانية، يعطي D-taro العدد الصحيح $A_2\ (=2000)$ إلى Anna.
يحقق هذا الإدخال النموذجي قيود جميع المهام الفرعية.