في الأول من يونيو ، جرت نهائيات بطولة البرمجة الخاصة بنا. أسماء الفائزين معروفة بالفعل. قريباً سيحصلون على جوائزهم ، وفي الوقت نفسه ، نبدأ في نشر تحليل لمهام البطولة. أولاً ، سنقوم بتحليل مهام مرحلة التأهيل بين مطوري الواجهة الخلفية.
تستمر المؤهلات أسبوعًا ، كما أن عدد المشاركين بالآلاف ، وبالتالي ، لا يعد إعداد المهام مهمة سهلة. في المجموع ، كان علينا القيام بـ 24 مهمة وتقسيمها بين الخيارات الأربعة بحيث تكون الخيارات قابلة للمقارنة في التعقيد.
هذه المرة توصلنا إلى ست مهام ، لكل منها كان من الممكن الخروج بعدة صيغ بديلة: أدت مهمة واحدة اخترعت إلى أربعة في وقت واحد! وبالتالي ، تحولت الخيارات لتكون قابلة للمقارنة قدر الإمكان.
لذلك ، لن أنشر تحليلات لكل المشكلات الـ 24. بدلاً من ذلك ، سأقوم بتحليل المهام الست لإحدى خيارات التأهيل: يتم حل الآخرين بطريقة مماثلة.
أ. الإنذارات
شرط المهمةيتمتع العمل في معظم شركات تكنولوجيا المعلومات بالعديد من المزايا: لا يوجد نظام لباس ، يمكنك في بعض الأحيان العمل عن بعد ، زملاء باردين وذكيين ، وبالطبع جدول مجاني! ومع ذلك ، فإن الجدول الزمني المجاني والقدرة على العمل عن بعد يتطلبان الكثير من قوة الإرادة.
مبرمج اليكسي يحب العمل ليلا ولا يحب أن يأتي للعمل متأخرا. للاستيقاظ بالضبط في الصباح ، يبدأ Alexey كل ليلة N إنذارات على هاتفك. يتم ضبط كل منبه حتى يرن كل مرة X دقائق من النقطة في الوقت الذي أحضر. على سبيل المثال ، إذا تم ضبط المنبه في وقت ما ti ثم سيتصل في بعض الأحيان ti . ti+X . ti+2 cdotX إلخ. في نفس الوقت ، إذا بدأ أي من أجهزة الإنذار في الرنين في لحظة واحدة من الوقت ، فسيتم عرض واحد منهم فقط.
من المعروف أنه قبل الاستيقاظ ، يستمع أليكسي إلى كل صباح K المنبه ، وبعد ذلك يستيقظ. تحديد النقطة في الوقت المناسب عندما يستيقظ أليكس.
يتم رنين جميع الإنذارات في أوقات عدد صحيح ، وجميع أجهزة الإنذار لها نفس فترة غفوة المكالمة. إذا تم تعيين اثنين من أجهزة الإنذار في نقاط زمنية ti و tj ، وهذه النقاط في الوقت تعطي نفس الباقي عند القسمة على X ، يمكنك ترك المنبه واحد فقط - واحد الذي يرن الأول.
لذا فإن الخطوة الأولى هي التخلص من الإنذارات غير الضرورية: سنقوم بتجميعها حسب قيمة باقي القسمة بواسطة X ومن كل مجموعة ، سنترك ساعة منبه واحدة فقط في أقرب وقت ممكن.
الآن سنتعرف على كيفية تحديد عدد أجهزة الإنذار التي تحدث في وقت معين T . إذا تم ضبط المنبه في الوقت المحدد ti ، عدد مكالماته بحلول الوقت T سوف تكون متساوية
max Big( fracT−tiX،0 Big).
بإضافة هذه القيم لجميع أجهزة الإنذار ، نحصل على العدد الإجمالي لأجهزة الإنذار الرنين حسب الوقت T .
بعد ذلك ، يتم حل المشكلة الأولية عن طريق البحث الثنائي بواسطة T : مع زيادة T لا ينخفض عدد أجهزة الإنذار بالرنين (أي أن الدالة رتابة) ؛ يمكنك تحديد 0 على أنها الحد الأيسر الأولي ، والحد الأقصى للإجابة الممكنة في المشكلة مع الحد الأيمن.
B. بطولة رياضية
شرط المهمةبينما كانت ماشا في إجازة ، نظّم زملاؤها بطولة شطرنج في النظام الأولمبي. خلال الفترة الباقية ، لم تهتم ماشا بهذا المشروع ، لذا بالكاد تتذكر من لعب مع من (حول ترتيب الألعاب ، ليس هناك شك). فجأة ، حصلت ماشا على فكرة أنه سيكون من الجيد إحضار هدية تذكارية من العطلة إلى الفائز بالبطولة. لا تعرف ماشا من فاز في المباراة النهائية ، لكنها تستطيع بسهولة معرفة من شارك فيها ، إذا تذكرت بشكل صحيح أزواج اللعب. ساعدها في التحقق مما إذا كان هذا هو الحال وتحديد المرشحين المحتملين للفائزين.
يمكن حل هذه المشكلة عن طريق استعادة الرسم البياني لألعاب البطولة. بادئ ذي بدء ، من الواضح لكل مشارك ما هي المرحلة من البطولة التي وصل إليها: يتم تحديد ذلك حسب عدد الألعاب بمشاركته.
بعد ذلك ، يمكنك توزيع الألعاب على الجولات. قل ، في جميع مباريات الجولة الأولى ، أقلع أحد المشاركين في الجولة الأولى ، والآخر أقلعت في وقت سابق عن الجولة الثانية. عند معالجة لعبة جولة برقم x من الضروري التحقق من أن جميع المشاركين في هذه اللعبة لعبوا حاليًا نفس عدد الألعاب المطابقة للرقم x وإلا فإن البطولة غير صالحة.
بعد استعادة مخطط البطولة ، كل ما تبقى هو استنتاج الجواب.
لعبة مثيرة للاهتمام
شرط المهمةيلعب Petya و Vasya لعبة مثيرة للاهتمام. أولاً ، تعلن Vasya عن عدد النقاط التي تحتاجها للتسجيل حتى تنتهي اللعبة. ثم يأخذ بيتيا البطاقات المكتوبة على أعداد صحيحة غير سالبة ، ويبدأ في وضعها على الطاولة واحدة تلو الأخرى. إذا كان هناك مضاعفات من خمسة على البطاقة ، فإن فازيا يحصل على نقطة واحدة. إذا كان هناك مضاعفات ثلاث على البطاقة ، فستحصل نقطة واحدة على Petya. إذا كان هناك رقم على البطاقة لا يتعدى ثلاثة أو خمسة ، أو بالعكس ، مضاعف لكل منهما ، فلا أحد يحصل على نقاط.
بمجرد حصول أحد المشاركين على عدد النقاط التي حددها Vasya في بداية اللعبة ، تتوقف اللعبة ويصبح هذا اللاعب هو الفائز. إذا لم يسجل أي من المشاركين العدد المطلوب من النقاط ، ولكن في الوقت نفسه انتهت جميع البطاقات ، فسيعتبر اللاعب الذي حصل على أكبر عدد من النقاط هو الفائز. إذا انتهت جميع البطاقات ، وتم تقسيم النقاط بالتساوي ، يتم الإعلان عن السحب.
في بعض الأحيان يتعجل Petya و Vasya ، لذلك لا يرغبان في لعب اللعبة بشكل كامل ، ولكنهما يكتشفان على الفور من سيفوز بالبيانات الأولية المعروفة. طلبوا منك كتابة برنامج يساعد في الإجابة على هذا السؤال.
أهم شيء في هذه المهمة هو الفهم الصحيح للشرط من بين اللاعبين وعدد النقاط التي يتم منحها بعد كل خطوة جديدة وأيضًا تحت أي ظروف يكسبها اللاعب.
يتم حل المشكلة بطريقة مباشرة. نظرًا لأن القيود أكثر من اللطيفة ، يكفي أن نراجع البيانات مرة واحدة ، ونوقف معالجتها ، إذا سجل أحد اللاعبين في الخطوة التالية العدد المطلوب من النقاط. إذا لم يسجل أي من اللاعبين الحد الأدنى المطلوب من النقاط ، يتم تحديد الفائز في نهاية الدورة.
في بعض إصدارات هذه المهمة ، كان من الضروري زيادة التعامل مع الموقف حيث يمكن للاعبين استلام النقاط في نفس الوقت للحصول على نفس البطاقة.
هذه المهمة كانت الأسهل بين جميع مهام التأهيل.
محلل استثناء
شرط المهمةنحن تصف بناء جملة لغة البرمجة EX :
func f() {...} - إعلان دالة (بين قوسين - النص)maybethrow Exc هو أمر قد يلقي استثناء من النوع Exc ، أو قد لا يرمي.try {...} suppress Exc - إذا حدث استثناء من النوع Exc داخل هذه الكتلة ، فسيتم كبحه.f() هي دعوة إلى f .
في اللغة EX جميع التعليمات ، باستثناء إعلانات الوظائف ، لا يمكن أن تكون إلا في نص وظيفة ما. لا يمكن الإعلان عن الوظائف داخل وظائف أخرى. يمكن استدعاء الوظيفة قبل تعريفها ، وكذلك في جسمها. أسماء الوظائف والاستثناءات في اللغة EX يجب أن تتطابق مع التعبير العادي [a−zA−Z0−9 ]+ ، تكون فريدة ولا تتطابق مع الكلمات الرئيسية func ، try ، suppress ، maybethrow .
برنامج في اللغة هو المدخلات EX والرقم x . لكل وظيفة من البرنامج ، لا أكثر من x الاستثناءات التي قد تطير منه. يجب الإخراج x أصغر الاستثناءات المعجمية.
تبين أن هذه المهمة هي أصعب مهام التأهيل.
لحلها ، كان من الممكن تحليل البرنامج بناءً على ذلك من خلال إنشاء رسم بياني لمكالمات الوظائف: في هذا الرسم البياني ، تتطابق كل وظيفة مع قمة ، ومكالمة دالة ، حافة. بعد ذلك ، من الضروري التنفيذ المباشر لمنطق توزيع الاستثناءات عبر الرسم البياني - لذلك ، يكون عرض الرسم البياني المناسب مناسبًا.
سنختار بعض الاستثناءات وجميع الوظائف التي يمكن أن تؤدي إلى ذلك. تسمى هذه الوظائف من وظائف أخرى ؛ ربما تكون المكالمات موجودة داخل try {...} suppress block block - في هذه الحالة لا ينطبق الاستثناء على الوظيفة التي تحدث فيها المكالمة. وبالتالي ، من الممكن تحديد جميع الوظائف التي يمكن من خلالها طرح هذا الاستثناء باستخدام اجتياز عرض الرسم البياني.
بعد تنفيذ التجاوز لجميع الاستثناءات الممكنة ، يبقى فقط لتشكيل إجابة.
E. فك التشفير
شرط المهمةظهرت خدمة جديدة على الإنترنت. لسوء الحظ ، ليس لديه وثائق. من الناحية التجريبية ، تم استلام السلسلة s من الخادم. ومع ذلك ، يتم تشفير بعض الأحرف في هذا السطر - للحصول على إجابة حقيقية ، تحتاج إلى فك تشفير هذا السطر عدة مرات. نظرًا لعدم وجود وثائق للخدمة ، لإجراء مزيد من التجارب ، من الضروري تحديد الحد الأقصى لعدد المرات التي يمكن فك تشفير هذا الخط فيها بطريقة غير تافهة. إن إجراء فك التشفير هو كما يلي: تحتاج إلى العثور على جميع سلاسل فرعية للنموذج ~XY ، حيث يكون X و Y من الأرقام السداسية العشرية الكبيرة أو الصغيرة واستبدالها في وقت واحد بحرف مع رمز ASCII 
(كل سلسلة فرعية لها قناعاتها). يسمى فك التشفير تافهة إذا لم يكن هناك أي سلاسل من هذا النوع.
في سطر واحد ، اطبع العدد الأقصى لفك التشفيرات غير التافهة المتتالية للسلسلة الأصلية.
سننظر في أحرف سلسلة المصدر بالتسلسل ، من اليسار إلى اليمين. إذا أدت إضافة شخصية أخرى إلى تسلسل يمكن فك تشفيره ، فأنت بحاجة إلى القيام بذلك. يجب تكرار فك التشفير لأطول فترة ممكنة ، أي بينما في نهاية السطر الحالي ، يوجد تسلسل للنموذج المحدد بواسطة شروط المهمة.
لكل حرف من السلسلة التي تم فك شفرتها الناتجة ، يجب أن تتذكر عدد مرات الحصول عليها لفك تشفير السلسلة الأصلية. من الواضح أن الحرف المضاف إلى السلسلة يتم فك تشفيره صفر مرة. إذا كانت الرموز فك الشفرة المشاركة في عملية فك التشفير التالية r1،r2،...،rk مرات ، ثم الرمز الذي شكلوه يتطلب بحدأقصى(r1،r2،...،rk)+1دولا عمليات فك التشفير.
دع السلسلة النهائية المشفرة تحتوي على أحرف a1،...،ak ، للحصول على ما هو ضروري لتنفيذ فك التشفير ، على التوالي ، r1،...،rk الوقت. ثم الجواب هو الكمية
بحدأقصى(r1،...،rk).
F. العثور على التزام كسر
شرط المهمةتطبق Yandex Search سياسة "الجذع الأخضر" المزعومة: أي رمز يدخل المستودع ، مع بعض التحفظات ، يُضمن عدم كسر التجميع والاختبارات.
الاختبارات ، مع ذلك ، صعبة للغاية ، وإدارة كل منهم على كل التزام غير عملي. لذلك بالنسبة للحالات الصعبة بشكل خاص ، يتم تنفيذ الإجراء التالي: يتم إجراء الاختبارات مع بعض الانتظام ، ويتم فحص مجموعة من الالتزامات على الفور. وبالتالي ، قد تقع الوقائع غير المختبرة في الصندوق لفترة من الوقت ، ومن بينها واحدة على الأقل تحتوي على خطأ.
في مثل هذه الحالة ، يجب على نظام الاختبار الكشف عن عدد m للالتزام الأول الذي كسر الاختبارات. يحتوي هذا الرقم على الخاصية التالية: جميع التعيينات بأرقام أقل من اختبارات النجاح m ، وتلتزم بأرقام أكبر من أو تساوي اختبارات فشل m. تضمن المهمة أن الالتزام بالخصائص المحددة موجود بالضرورة وهو فريد من نوعه.
من أجل توفير الموارد ، يمكن لنظام الاختبار التحقق من التزام واحد فقط في كل مرة. تحتاج إلى كتابة برنامج يحدد العدد م.
تحتوي هذه المهمة على نموذج أولي في إنتاجنا: بعض اختبارات مكونات البحث معقدة للغاية ، وهي مكلفة للغاية لتشغيلها لكل التزام ، ويتم تنفيذ الإجراء الخاص بهم لإيجاد أعطال مماثلة لتلك الموصوفة في المهمة. بالطبع ، يمكن للمطورين استخدام التحقق المسبق ، وكقاعدة عامة ، القيام بذلك ، لذلك هذا الإجراء ليس شائعًا.
اختلفت الإصدارات المختلفة للمهمة في عدد الإلتزامات التي يجب التحقق منها في نفس الوقت.
الحل هنا بسيط للغاية: تحتاج إلى تنفيذ إصدار أكثر تعقيدًا من البحث الثنائي . لنفترض أنك إذا أردت التحقق من أربعة أوامر في وقت واحد ، فأنت بحاجة إلى تقسيم الجزء الحالي بالتساوي بأربعة أرقام. أثناء التنفيذ ، يجب توخي الحذر لتجنب الحلقات عندما يكون طول المقطع أقل من عدد التعيينات المحددة في وقت واحد. تجدر الإشارة أيضًا إلى أنه ، وفقًا لشروط المشكلة ، يمكنك التحقق من الالتزام نفسه عدة مرات - في بعض الأحيان يتعين عليك القيام بذلك ، على سبيل المثال ، إذا كان هناك مجموعتان من الالتزامات ، وتحتاج إلى التحقق من ثلاث مرات في وقت واحد.
تتوفر مهام جولة التأهيل التي تمت مناقشتها كتدريب Codeforces . كما قمنا بتدريب على مهام النهائيات .