مقدمة
بالفعل في أكتوبر 2018 ، تذكرنا بكل سرور تقويم Advent مع مهام عام 2017 (الظروف
هنا ) وبدأنا في التفكير فيما يمكن القيام به هذا العام. من بين العديد من الأفكار الجديرة ، اخترنا خيارًا نختار فيه مهام "جذابة" متنوعة ، توحدها قصة رأس السنة الجميلة.
لم يتبق شيء: في الواقع ، استلم المهام ، وقم بتكوين قصة ، وقم بإنشاء موقع على شبكة الإنترنت مع المتصدرين ، جميل ومترابط بإحكام مع Yandex.Constest ، وابدأ في أوائل ديسمبر :-)
النتيجة
كما تعلمون ، فإن الشهية تأتي مع الأكل ، وقد هبطنا في عملية تحديد محتوى المهام وتنفيذها الفني. كل اكتشاف ناجح ألهم المزيد من التحسينات. ونتيجة لذلك ، قمنا برفع خادم منفصل لإحدى المهام ، وجعلنا الخادم الآخر تحسينًا واحدًا (ما زلنا لا نملك إجابة دقيقة) ، وسجلنا الموسيقى بأنفسنا ، وأعدنا التوزيعات - لم نشعر بالملل!
والنتيجة هي:
- 11 مهمة (+1 مكافأة) متفاوتة الصعوبة ، كل ذلك مع التحقق في المسابقة ؛
- موقع خارجي للمشاركين ؛
- 11 يوما (من 7 ديسمبر إلى 17 ديسمبر شاملة) لحل المشاكل.
حقائق وقصص مثيرة للاهتمام
780 مشاركاً مسجلاً ، بدأ 333 شخصًا في حل المشكلة ، ومرت 203 أشخاص بنجاح على الأقل مهمتين
في البداية ، قدرنا الوقت الصافي لحل جميع المشكلات في سبعة أيام لمشارك غير مستعد ويومين لخبير من ذوي الخبرة (يُعرف أيضًا باسم خريج مركز خدمة العملاء). تم إكمال المساعد الأول لسانتا كلوز الذي حل جميع المهام الإحدى عشرة بشكل صحيح لمدة يوم واحد ، وتمكنت اثنتان أخريان من الثانية!
رسالة من أحد المشاركين: "مساء الخير! بسبب المسابقة الخاصة بك ، أوقفت المكتب (40 شخصًا) على وجه التحديد المهمة الثانية حول قهوة سانتا كلوز ، أعطني تلميحًا من فضلك. كلنا معذبون للغاية. "
تحليل المهام
الشروط
هنا .
المهمة د "رسالة موسيقية" (ميخائيل بلوتكين)الأمر بسيط للغاية لحل المشكلة ، مع الحد الأدنى من التعليم الموسيقي.
محاولة للعثور على فكرة في النمط الإيقاعي لم تؤدي إلى النجاح. كانت الفكرة التالية هي الجلوس على البيانو والتقاط النغمة التي استمعت إليها. اتضح لا ، دو ، مي ، سي ، لا ، إعادة ، ملح ، مي. في المفتاح الموسيقي ثلاثة أضعاف مثل هذا:
بعد الملاحظات الثلاثة الأولى ، تبع وقفة قصيرة ، كما لو أن تقسيم العبارة الموسيقية إلى كلمتين. بقي فقط لكتابة الملاحظات في تدوين الحروف التقليدية (A = la ، B = si ، C = do ، D = pe ، E = mi ، F = fa ، G = ملح) وكلمتين مفتوحتين: ACE BADGE.
وبدون معرفة المعرفة الموسيقية ، يصبح حل المشكلة أكثر صعوبة. على سبيل المثال ، يمكن للمرء استخدام بعض البرامج لمعالجة الصوت ومعرفة الملاحظات نفسها أو ترددات الأصوات في هرتز ، ثم معرفة الترددات التي تتوافق مع الملاحظات.
المهمة المطلوبة لكتابة الرسائل معًا بدون فواصل ، وبالتالي فإن الإجابة هي ACEBADGE.
المهمة F "حقيبة الثلج" (ميخائيل بلوتكين)مساحة المثلث الأولي هي 1. بعد ذلك ، في الخطوة nth ، تتم إضافة مثلثات t_n ، ولكل منها مساحة s_n. يتم التعبير عن إجمالي مساحة الشكل الناتج كمجموع لسلسلة لانهائية:
S = 1 + Σ (t_n * s_n) ، المجموع على n هو من 0 إلى ∞ (1)
في الخطوة الصفرية ، t_0 = 3 ، s_0 = 1/9 ، نظرًا لأن المثلث له 3 جوانب ، حيث يكون المثلث مبنيًا على جانب أصغر بثلاث مرات من الأصل ، وبالتالي مساحة أصغر 9 مرات من مساحة المثلث الأصلي.
في كل خطوة تالية ، يتحول كل جانب إلى أربعة جوانب أصغر ثلاث مرات ، أي
t_n = t_ {n-1} * 4 = t_0 * 4n = 3 * 4n ،
s_n = s_ {n-1} * (1/9) = s_0 * (1/9) ^ n = 1/9 * (1/9) ^ n.
لذلك ، المنطقة المطلوبة:
S = 1 + Σ (t_n * s_n) = 1 + 1/3 * Σ ((4/9) ^ n) ، المجموع على n هو من 0 إلى ∞ (2)
المصطلح الثاني هو مجموع تقدم هندسي متناقص. لحسابها ، استخدم صيغة المدرسة
Σ ((4/9) ^ n) = 1 / (1 - 4/9) = 9/5.
استبدال في الصيغة (2) ، نحصل على الجواب:
S = 1 + 1/3 * 9/5 = 8/5 = 1.6
المهمة G و L "تم بناء المسار" (أرتيوم رومانوف)بفضل Artyom
mehrunesartem للحل! بالمناسبة ، يعتمد الرسم البياني الذي تم استخدامه في Problem G على London Underground :)
لحل هذه المشكلة ، سوف نستخدم نسخة معدلة من البحث الأول المتسع. نحصل على قمة (مصدر) وهمية ، والتي نرسم منها حوافًا ذات وزن صفري في كل قمة من الرسم البياني. يتم تحديد كل ولاية بشكل فريد من خلال المسار الذي تم تمريره من المصدر. بالإضافة إلى ذلك ، سنقوم بتخزين الوقت الذي يقضيه والبهجة المستلمة.
نبدأ قائمة انتظار ذات أولوية ثابتة ، حيث سنضع الحالة. كتقييم للظروف في قائمة الانتظار ، سوف نستخدم نسبة السعادة المستلمة إلى الوقت الذي يقضيه. هذا التقييم غير صحيح ، لكنه أظهر نتائج جيدة في هذه المهمة.
في كل خطوة ، سوف نحصل على الولاية بأفضل تقدير من قائمة الانتظار ونضع الحالات التي تم تشكيلها منها في قائمة الانتظار. مع هذا النهج ، سوف يستغرق الأمر وقتًا طويلاً للحصول على النتيجة النهائية.
لتسريع الحل ، سوف نبحث عن الإجابة خطوة بخطوة. في كل خطوة ، للبحث عن القمة التالية في المسار ، سنقوم بمسح قائمة الانتظار ووضع الحالة الحالية فيه. ثم سنقوم بعدد ثابت من الخطوات ، مع تحديث الحالة التي تعطي أكبر قدر من السعادة في نفس الوقت. كقمة تالية للمسار ، نأخذ قمة الرأس بعد آخر قمة للحالة الحالية في مسار الحالة الناتجة التي تعطي أكبر قدر من السعادة. نكرر الإجراءات التي تم تنفيذها حتى نتمكن من تحسين الحالة الحالية.
التحسينات الممكنة
- استخدام أفضل الاستدلال.
- مع هذا التطبيق للخوارزمية ، ستظهر حالات إضافية ، حيث سنضيف في كل خطوة جميع الحالات التي يمكن أن تأتي من الحالة الحالية. لمنع هذا ، باستخدام خوارزمية Dijkstra ، لكل قمة من الرسم البياني ، يمكنك أولاً إنشاء شجرة من أقصر الطرق لجميع القمم الأخرى وإجراء انتقالات ليس في خطوة واحدة ، ولكن على طول الشجرة التي تم بناؤها حتى نصل إلى القمم التي لم نذهب إليها من قبل.
لم تقدم هذه التغييرات تحسينات كبيرة ، على الأرجح بسبب وجود اختبار مغلق واحد فقط ، وليس مجموعة من الاختبارات المتولدة المختلفة.
المهمة الأولى "محوّلو الدببة" (ألكسندر ساموفالوف)دعونا نلقي نظرة على
الكود المصدري للخدمة .
يمكن الحصول على قائمة بجميع المعرفات المتاحة للمستخدم على
/data .
إذا كان هناك معرف ، فيمكن الحصول على البيانات باستخدام طلب إلى العنوان
/data/id .
للوصول إلى البيانات ، تتطلب الخدمة رمزًا للمصادقة. لدينا
رمز مميز متاح ، ولكن انتهت صلاحيته ولم تعد الخدمة تقبله.
دعونا نرى في الكود
كيف يتم إنشاء هذه الرموز . يتم الحصول على الرمز المميز عن طريق تشفير JSON للنموذج
{ “userId” : “id”, expireDate: “date”} ثم تشفيره في base64. تستخدم الخدمة RSA للتشفير ، ويمكن الحصول على المفتاح العمومي حسب الطلب عند
/key .
لنقدم طلبًا: e = 30593 ، n = 66043. ومنذ ذلك الحين n صغير بما يكفي ، ثم يمكننا حساب المفتاح الخاص بسهولة.
للقيام بذلك ، نحلل n إلى العوامل الأولية: 211 * 313.
نحسب
وظيفة أويلر n: φ (n) = (211 - 1) (313 - 1) = 65520.
نحصل على d = e-1 (mod φ (n)) = 257.
يمكن حساب معامل العنصر العكسي باستخدام
خوارزمية الإقليدية المتقدمة .
بعد حساب المفتاح الخاص ، نقوم بفك تشفير الرمز المميز المتاح لنا.
حصلنا على JSON التالية:
{"userId":"448f0a79-e2d8-4ccd-9009-53858914dcaa","expireDate":"2018-12-06T14:38:00.898026+00:00"}لاحظ أنه
يكفي وجود خدمة للمستخدم ذي userId المحدد وتنتهي مدة صلاحيته ليكون أقل من الوقت الحالي على الخادم.
بمعنى userId ، يمكننا إنشاء رمز مميز جديد صالح.
للقيام بذلك ، خذ expireDate كبيرة بما يكفي لاجتياز الاختبار - على سبيل المثال
{"userId":"448f0a79-e2d8-4ccd-9009-53858914dcaa","expireDate":"2100-01-01T12:00:00.000000+00:00"} .
نقوم بتشفير الرمز المميز الجديد باستخدام المفتاح العمومي.
بعد تقديم طلب
/data ، اكتشفنا أن المستخدم أنشأ رسائل ذات معرفات من 1 إلى 4.
سنقوم بترتيب كل منهم.
من بينها عبارة رائعة:
سنة جديدة تطرق الباب ، وافتحها قريبًا! .
نصائح لحل بعض المشكلات الأخرى (من Artyom Romanov)المهمة أ "آمنة مع الحروف"قد تلاحظ أنه في كل عشرين خطوة ستحصل على نفس الرقم.
المهمة ب "سر الأستاذ"فرز الكلمات بترتيب تنازلي من شعبية. قد تلاحظ أن كل كلمة لاحقة تحدث في حوالي 2 ، 3 ، 4 ، إلخ. مرات أقل من الكلمة الأكثر شعبية. الآن يمكنك استعادة الجواب.
المهمة C "كارثة الكمبيوتر"فكر في لغة برمجة مساحة بيضاء.
المهمة J "البنغال"موضع ممكن:
المشكلة ك "نمط فاترة"لحل هذه المشكلة ، يمكنك اختيار أي مثلث مناسب ، على سبيل المثال الصحيح ، وحساب الإجابة عليه.
شكر وتقدير
كانت العملية برمتها من الفكرة إلى التنفيذ مدفوعة ومنسقة من قبل Katya Lebedeva. لقد ساعدتها أنا كاتيا أرتامونوفا وألينا موزينا وساشا كوميساروف في إكمال المهام. كتب ليوشا Tolstikov ثلاثة لعبة الداما المعقدة ، صنع ساشا Komissarov وسريوزا Zherevchuk الخادم ، صنع Svyato و Seryozha موقع على شبكة الإنترنت جميلة مع تكامل وثيق مع المهام: يمكن لكل مشارك رؤية تقدمه والمتصدرين.