QOJ.ac

QOJ

Limite de temps : 3 s Limite de mémoire : 512 MB Points totaux : 100 Difficulté: [afficher] Interactif

#194. كلمة المرور

Statistiques

لقد نسيت كلمة المرور الخاصة بي مرة أخرى! أنا أجلس أمام حاسوبي وأكتب كلمات مرور خاطئة. كل ما أتذكره هو أن كلمة المرور تحتوي على أحرف صغيرة فقط. لحسن الحظ، يستجيب نظام تسجيل الدخول بأكثر من مجرد «كلمة مرور خاطئة». فهو يخبرني أيضًا بطول أطول بادئة من مُدخلي تظهر بوصفها متتالية جزئية (ليست بالضرورة متجاورة) في كلمة المرور. وبشكل رسمي، من أجل كلمة مرور $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".

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
EditorialOpen Official EditorialQingyu- Download

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.