# تحدي السجناء في أحد السجون ، يوجد $500$ سجين. وفي يوم من الأيام ، قدم آمر السجن فرصة لهؤلاء السجناء لتحرير أنفسهم. قام آمر السجن بوضع حقيبتي نقود في غرفة ما، حقيبة A وحقيبة B تحتوي كل منهما عدداً بين $1$ و$N$ من القطع النقدية، ضمناً. يكون عدد القطع النقدية الموجودة في الحقيبة A **مختلفاً** عن عدد القطع النقدية الموجودة في الحقيبة B. يتحدى آمر السجن السجناء. حيث يكون هدف السجناء تعيين الحقيبة التي تحتوي عدداً أقل من القطع النقدية. تحتوي الغرفة على لوح أبيض بالإضافة إلى حقيبتي النقود. سيكون هنالك رقماً وحيداً مكتوباً على اللوح الأبيض في كل لحظة. يكون الرقم المكتوب على اللوح الأبيض بداية هو $0$. يطلب آمر السجن من السجناء الدخول إلى الغرفة، واحداً تلو الآخر. لا يعلم السجين الداخل إلى الغرفة من أو كم سجين سبقه بالدخول إليها. في كل مرة يدخل سجين ما إلى الغرفة، يقرأ الرقم المكتوب حالياً على اللوح الأبيض. وبعد ذلك، يجب أن يختار السجين إما الحقيبة A أو الحقيبة B. **يتفقد** السجين محتويات الحقيبة التي اختارها، وبالتالي يعلم عدد القطع التقدية التي تحتويها الحقيبة. ثم يتوجب على السجين القيام بأحد **الأفعال** التالية: * يستبدل الرقم المكتوب على اللوح الأبيض برقم صحيح غير سالب ومن ثم يغادر الغرفة. لاحظ أنه من الممكن للسجين تغيير الرقم المكتوب على اللوح الأبيض أو الاحتفاظ به. ومن بعدها يستمر تحدي آمر السجن للسجناء (عدا في حالة تم دخول الـ$500$ سجين جميعاً إلى الغرفة) * تعيين الحقيبة التي تحتوي عدداً أقل من القطع النقدية. ينهي هذا الفعل التحدي مباشرة. لن يطلب آمر السجن من اي سجين دخل الغرفة مسبقاً معاودة الدخول إليها مرة أخرى. يربح السجناء التحدي في حال قام أحدهم بتعيين الحقيبة التي تحتوي عدداً أقل من القطع النقدية. فيما يخسر السجناء التحدي في حال قام أحدهم بتعيين الحقيبة بشكل خاطئ، أو تم دخول الـ$500$ سجين جميعاً إلى الغرفة ولم يقوموا بتعيين الحقيبة التي تحتوي عدداً أقل من القطع النقدية. قبل بدء التحدي، يجتمع السجناء في صالة السجن ويتفقون على **استراتيجية** مشتركة التحدي بثلاثة خطوات: * يختارون عدداً صحيحاً غير سالباً $x$، يعبر عن أكبر عدد يرغبون بكتابته على اللوح الأبيض. * من أجل أي رقم $0 \le i \le x$ مكتوب على اللوح الأبيض، يتفق السجناء على الحقيبة التي يتوجب على السجين تفقد محتوياتها بعد دخول الغرفة. * يتفق السجناء على الفعل الذي يتوجب على السجين الداخل للغرفة القيام به بعد معرفته لعدد القطع النقدية الموجودة في الحقيبة التي اختارها. بشكل أكثر دقة: ومن أجل أي رقم $0 \le i \le x$ مكتوب على اللوح الأبيض، ومن أجل أي عدد $1 \le j \le N$ من القطع النقدية الموجودة في الحقيبة التي تم اختيارها، يتم الاتفاق على: - ما هو الرقم (بين $0$ و$x$، ضمناً) الذي يجب كتابته على اللوح الأبيض، أو - أي حقيبة يجب تعيينها على أنها الحقيبة التي تحتوي عدداً أقل من القطع النقدية. في حالة ربح السجناء للتحدي، سيقوم آمر السجن بإطلاق سراحهم بعد $x$ يوم إضافي في السجن. تحدد مهمتك بإبتكار استراتيجية للسجناء تضمن ربحهم في التحدي (بغض النظر عن عدد القطع النقدية الموجودة في الحقيبة A والحقيبة B). تعتمد علامة الحل على قيمة $x$ (انظر إلى فقرة Subtasks للتفاصيل) ## تفاصيل التحقيق يجب عليك تحقيق التابع التالي: ``` int[][] devise_strategy(int N) ``` * $N$: العدد الأعظمي الممكن لعدد القطع النقدية في أي من الحقيبتين * يجب أن يعيد التابع مصفوفة $s$ من مصفوفات تحتوي كل منها $N + 1$ رقماً صحيحاً، تعبر عن استراتيجيتك. تكون قيمة $x$ هي طول المصفوفة $s$ ناقصاً واحد. من أجل $0 \le i \le x$، تمثل المصفوفة $s[i]$ الفعل الواجب على السجين فعله عندما يقرأ الرقم $i$ على اللوح الأبيض بعد دخول الغرفة: 1. تكون القيمة $s[i][0]$ مساوية $0$ إذا كان على السجين تفقد محتويات الحقيبة A، أو $1$ إذا كان عليه تفقد محتويات الحقيبة B. 2. لتكن $j$ هو عدد القطع النقدية الموجودة في الحقيبة التي تم اختيارها. يجب على السجين القيام بما يلي: * إذا كانت القيمة $s[i][j]$ مساوية $-1$، يجب على السجين تعيين الحقيبة A على أنها الحقيبة التي تحتوي على عدد أقل من القطع النقدية. * إذا كانت القيمة $s[i][j]$ مساوية $-2$، يجب على السجين تعيين الحقيبة B على أنها الحقيبة التي تحتوي على عدد أقل من القطع النقدية. * إذا كانت القيمة $s[i][j]$ عدداً غير سالب، يجب على السجين كتابة الرقم $s[i][j]$ على اللوح الأبيض. لاحظ أن $s[i][j]$ يجب أن لا يتجاوز $x$. * يتم استدعاء هذا التابع مرةً واحدةً فقط. ## مثال ليكن الاستدعاء التالي: ``` devise_strategy(3) ``` وليكن $v$ الرقم الذي يقرؤه السجين على اللوح الأبيض عندما يدخل للغرفة. فيما يلي واحدة من الاستراتيجيات الصحيحة: - إذا كانت $v = 0$ (متضمناً الرقم الابتدائي)، تفقد محتويات الحقيبة A. - إذا كانت تحتوي على $1$ قطعة نقدية، عيّن الحقيبة A على أنها الحقيبة التي تحتوي عدداً أقل من القطع النقدية. - إذا كانت تحتوي على $3$ قطع نقدية، عيّن الحقيبة B على أنها الحقيبة التي تحتوي عدداً أقل من القطع النقدية. - إذا كانت تحتوي على $2$ قطع نقدية، اكتب الرقم $1$ على اللوح الأبيض (مستبدلاً الرقم $0$). - إذا كانت $v = 1$، تفقد محتويات الحقيبة B. - إذا كانت تحتوي على $1$ قطعة نقدية، عيّن الحقيبة B على أنها الحقيبة التي تحتوي عدداً أقل من القطع النقدية. - إذا كانت تحتوي على $3$ قطع نقدية، عيّن الحقيبة A على أنها الحقيبة التي تحتوي عدداً أقل من القطع النقدية. - إذا كانت تحتوي على $2$ قطع نقدية، اكتب الرقم $0$ على اللوح الأبيض (مستبدلاً الرقم $1$). لاحظ أن هذه الحالة لن تحدث أبداً، لأن هذه الحالة تعني أن كلاً من الحقيبتين تحتوي على قطعتين نقديتين وهذا غير مسموح. للتصريح عن هذه الاستراتيجية، يجب أن يعيد التابع `[[0, -1, 1, -2], [1, -2, 0, -1]]`. طول المصفوفة المعادة هو $2$، مما يعني أن قيمة $x$ في هذه الحالة هي $2 - 1 = 1$.
## Constraints * $2 \le N \le 5000$ ## Subtasks 1. (5 points) $N \le 500$, the value of $x$ must not be more than $500$. 1. (5 points) $N \le 500$, the value of $x$ must not be more than $70$. 1. (90 points) The value of $x$ must not be more than $60$. If in any of the test cases, the array returned by `devise_strategy` does not represent a correct strategy, the score of your solution for that subtask will be $0$. In subtask 3 you can obtain a partial score. Let $m$ be the maximum value of $x$ for the returned arrays over all test cases in this subtask. Your score for this subtask is calculated according to the following table: Condition | Points :----------------:|:---------------------------: $40 \le m \le 60$ | $20$ $26 \le m \le 39$ | $25 + 1.5 \times (40 - m)$ $m = 25$ | $50$ $m = 24$ | $55$ $m = 23$ | $62$ $m = 22$ | $70$ $m = 21$ | $80$ $m \le 20$ | $90$ ## Sample Grader The sample grader reads the input in the following format: * line $1$: $N$ * line $2 + k$ ($0 \le k$): $A[k] \; B[k]$ * last line: $-1$ Each line except the first and the last one represents a scenario. We refer to the scenario described in line $2 + k$ as scenario $k$. In scenario $k$ bag A contains $A[k]$ coins and bag B contains $B[k]$ coins. The sample grader first calls `devise_strategy(N)`. The value of $x$ is the length of the array returned by the call minus one. Then, if the sample grader detects that the array returned by `devise_strategy` does not conform to the constraints described in Implementation Details, it prints one of the following error messages and exits: * `s is an empty array`: $s$ is an empty array (which does not represent a valid strategy). * `s[i] contains incorrect length`: There exists an index $i$ ($0 \le i \le x$) such that the length of $s[i]$ is not $N + 1$. * `First element of s[i] is non-binary`: There exists an index $i$ ($0 \le i \le x$) such that $s[i][0]$ is neither $0$ nor $1$. * `s[i][j] contains incorrect value`: There exist indices $i, j$ ($0 \le i \le x, 1 \le j \le N$) such that $s[i][j]$ is not between $-2$ and $x$. Otherwise, the sample grader produces two outputs. First, the sample grader prints the output of your strategy in the following format: * line $1 + k$ ($0 \le k$): output of your strategy for scenario $k$. If applying the strategy leads to a prisoner identifying bag A as the one with fewer coins, then the output is the character `A`. If applying the strategy leads to a prisoner identifying bag B as the one with fewer coins, then the output is the character `B`. If applying the strategy does not lead to any prisoner identifying a bag with fewer coins, then the output is the character `X`. Second, the sample grader writes a file `log.txt` in the current directory in the following format: * line $1 + k$ ($0 \le k$): $w[k][0] \; w[k][1] \; \ldots$ The sequence on line $1 + k$ corresponds to scenario $k$ and describes the numbers written on the whiteboard. Specifically, $w[k][l]$ is the number written by the ${(l+1)}^{th}$ prisoner to enter the room.