لقد نسيت كلمة المرور الخاصة بي مرة أخرى! أنا أجلس أمام حاسوبي وأكتب كلمات مرور خاطئة. كل ما أتذكره هو أن كلمة المرور تحتوي على أحرف صغيرة فقط. لحسن الحظ، يستجيب نظام تسجيل الدخول بأكثر من مجرد «كلمة مرور خاطئة». فهو يخبرني أيضًا بطول أطول بادئة من مُدخلي تظهر بوصفها متتالية جزئية (ليست بالضرورة متجاورة) في كلمة المرور. وبشكل رسمي، من أجل كلمة مرور $P = p_1 p_2 \dots p_N$ ومُدخل $Q = q_1 q_2 \dots q_N$، فإن إجابة نظام تسجيل الدخول هي أكبر قيمة لـ $L$ توجد من أجلها مؤشرات $1 \le k_1 < k_2 < \dots < k_L \le N$ بحيث يتحقق $q_i = p_{k_i}$ لكل $1 \le i \le L$. كما يخبرني النظام بقيمة $N$، وهي طول كلمة المرور، وبقيمة $S$، مما يعني أن كلمة المرور لا تستخدم سوى أول $S$ أحرف من الأبجدية. على سبيل المثال، $S = 4$ تعني أن كلمة المرور تحتوي فقط على الأحرف $\text{a}$ و$\text{b}$ و$\text{c}$ و$\text{d}$ (ولكن ليس بالضرورة جميعها).
أرجوك ساعدني على استعادة كلمة المرور الخاصة بي!
تفاصيل التنفيذ
هذه المسألة تفاعلية. يجب عليك تنفيذ الدالة
C: char* guess(int n, int s);
C++: string guess(int n, int s);
- المعاملات: $N$ و$S$ كما هو موضح أعلاه.
- القيمة المُعادة: كلمة المرور الصحيحة.
يمكن لبرنامجك استدعاء الدالة
C: int query(char* str);
C++: int query(string str);
- المعامل: سلسلة نصية مكوّنة من $1$ إلى $N$ حرفًا مختارة من بين أول $S$ أحرف في الأبجدية.
- القيمة المُعادة: عدد صحيح بين $0$ وطول
str، يمثل إجابة نظام تسجيل الدخول على استعلامك. - لتجنب أخطاء الترجمة البرمجية، يجب عليك التصريح عن هذه الدالة باستخدام النص أعلاه حرفيًا، في أي موضع ضمن النطاق العام قبل استدعائها.
- يمكنك استدعاء هذه الدالة على الأكثر $50\,000$ مرة لكل حالة اختبار.
يمكن لبرنامجك تعريف دوال إضافية.
مُصحِّح تجريبي
يُوفَّر ملف grader.{c,cpp} تجريبي لتختبر شيفرتك محليًا. يقرأ المُصحِّح التجريبي الإدخال من الملف password.in بالتنسيق الآتي:
- السطر $1$: $N$ $S$
- السطر $2$: كلمة المرور
يمكنك ترجمة المُصحِّح مع حلك برمجيًا، ثم تشغيل الملف التنفيذي الناتج لاختبار استراتيجية التخمين الخاصة بك على الإدخال المعطى.
المهام الفرعية
قد تُقيَّم حالات الاختبار كمجموعات. المهام الفرعية بالترتيب هي:
| المهمة الفرعية | نسبة النقاط | قيود الإدخال |
|---|---|---|
| 1 | 10% | $N \le S \le 26$؛ جميع الأحرف في كلمة المرور متمايزة |
| 2 | 20% | $2 \le N \le 100$ و$2 \le S \le 4$ |
| 3 | 20% | $2 \le N \le 2\,000$ و$2 \le S \le 20$ |
| 4 | 30% | $2 \le N \le 3\,500$ |
| 5 | 20% | $2 \le N \le 5\,000$ |
أمثلة
لتكن كلمة المرور هي $\text{aab}$. يستدعي المُصحِّح guess(3, 2). قد يكون سجل الاستدعاءات كما يلي:
| الاستدعاء | القيمة المُعادة |
|---|---|
guess("ab") |
2 |
guess("abb") |
2 |
guess("bab") |
1 |
guess("aab") |
3 |
عند هذه النقطة، يجب أن تعيد guess(3, 2) القيمة "aab".