تقديم الجوائز للمشاركين في المسار الخلفي
نحن نكمل سلسلة من تحليل بطولة البرمجة الثانية. في الأسابيع الأخيرة ، قمنا بنشر تحليل لثلاثة مسارات: ML ، الواجهة الأمامية وتطوير الهاتف المحمول. يبقى تحليل المسار على الواجهة الخلفية. اتضح أن الأكثر شعبية: شارك 2682 شخص في التصفيات ، 320 منهم وصلوا إلى النهائي. اخترع فريق Yandex.Taxi مهام مطوري الواجهة الخلفية.
الرموز الترويجية المريخية
المؤلف: مكسيم بيدشينكولقد مرت ستة أشهر منذ إطلاق Yandex.Taxi على المريخ. بحلول عام المريخ الجديد ، قررت Yandex.Taxi إعطاء رموز ترويجية للمريخيين. لكن اتضح أنه لا يمكن لـ Martians استخدام أكواد الترويجي Earth ، لأن الخوادم على المريخ لا تعمل وفقًا لقواعد Earth. لذلك ، جاء Yandex.Taxi مع الرموز الترويجية المريخية الخاصة.
يتم إنشاء رمز Martian الترويجي على النحو التالي:
- يتم إنشاء مفتاح تشفير.
- ينقسم مفتاح التشفير إلى سلاسل ذات طول عشوائي.
- من بين جميع العناصر الفرعية ، يتم تحديد سلاسل الطول L.
- يتم المختلط substrings ومتسلسل.
- نتيجة التسلسل هو رمز ترويجي.
الهدف:
من الضروري التحقق من صحة الشفرة الترويجية التي تم إدخالها. إذا كان الرمز الترويجي صالحًا ، فستحتاج إلى طباعة "نعم". إذا كانت غير صالحة ، "لا".
I / O التنسيقات والأمثلة والملاحظاتتنسيق الإدخال
<طول الرمز الترويجي>
<الرمز الترويجي>
<طول المفتاح>
<مفتاح>
<طول السلسلة الفرعية L>
تنسيق الإخراج
صلاحية رمز الترويج: نعم أو لا.
مثال 1
مثال 2
مثال 3
الملاحظات
طول L> 1.
رمز الترويج الأبجدي [AZ ، 0-9].
طول الشفرة الترويجية في النطاق [6 ، 30].
طول المفتاح في النطاق [6 ، 30].
طول السلسلة الفرعية L <طول المفتاح.
طول الرمز الترويجي هو مضاعف L.
قرار
نحن بحاجة إلى النظر في جميع الأقسام الممكنة من مفتاح التشفير في سلاسل فرعية بطول L وتحقق مما إذا كان يمكن أن يتكون رمز الترويجي هذا من أقسام محتملة.
التلميح مخفي في ملاحظات الحالة:
طول الشفرة الترويجية في النطاق [6 ، 30].
طول المفتاح في النطاق [6 ، 30].
تشير القيود الصغيرة إلى أن الحل الفعال غير مطلوب ، مما يعني أنك لست بحاجة إلى قضاء بعض الوقت في البحث عن التحسين - من الأفضل حل المشكلة مباشرةً.
هذا الموقف هو نموذجي لتطوير المنتجات الخلفية. غالبًا ما تكون هناك مواقف يمكنك فيها قضاء أسابيع على الخوارزمية المثلى ، ولكن إذا قمت بوزن القيود ، يصبح من الواضح أنه من الأفضل استخدام حل سريع وليس الحل الأمثل.
لذلك ، سننظر في السطر الذي يحتوي على الكود الترويجي كسلسلة فرعية من S S بطول L. لكل سلسلة فرعية S ، نجد أن جميع السلاسل الفرعية S
k تساويها من مفتاح التشفير. لكل S
k ، تذكر استخدامه ، وانتقل إلى السلسلة الفرعية التالية S وكرر الخوارزمية.
إذا تعذر عليك العثور على S غير مستخدمة في السلسلة الفرعية S ، فمن الضروري تجربة متغير آخر للتقسيم ، إذا لم يكن هناك متغير آخر ، فإن الرمز الترويجي غير صالح.
إذا تم العثور على S
k في حالة واحدة على الأقل لكل S ، فسيكون رمز الترويج صالحًا.
مارس نظام النقل الأمثل
المؤلفون: ديمتري بوليشوك وأنتون تودواكان عام 2058. كانت مستعمرات المستوطنين الأوائل قد هبطت بالفعل على سطح المريخ وبدأت في تسكنها ، وبدأت Yandex.Taxi في نشر نظام من محطات المكوك.
للتشغيل العادي ، تحتاج محطة المكوك إلى مصدر ثابت للطاقة من شبكة الطاقة. لتشغيل المحطة ، يجب عليك إما إنشاء مولد للطاقة النووية لليورانيوم داخل المحطة نفسها ، أو وضع كابل لمحطة مكوك أخرى (تعمل بالطاقة بالفعل). قد تختلف تكلفة بناء مولد داخل محطات النقل المختلفة. يختلف توجيه الكبل بين محطات المكوك أيضًا من حيث التكلفة وهو غير ممكن دائمًا. اتصال الكابل هو ثنائي الاتجاه.
تتمثل المهمة في تنظيم طاقة فعالة (بأقل تكلفة) لجميع محطات النقل.
عند المدخل ، يتلقى البرنامج إجمالي عدد محطات النقل ، وتكلفة إنشاء مولدات لكل محطة مكوكية ووصف لجميع الكابلات الممكنة بين محطات النقل (عدد المحطات المتصلة وتكلفة وضع الكابل).
I / O التنسيقات والأمثلة والملاحظاتتنسيق الإدخال
يحتوي
السطر الأول على عدد غير سالب واحد من محطات المكوك N-1000.
يحتوي
السطر الثاني على أرقام N التي تحدد تكلفة بناء المولد داخل المحطة المقابلة.
يحتوي
السطر الثالث على عدد غير سالب واحد من الكبلات المحتملة K ≤ 100000 بين محطات المكوك.
تحتوي الأسطر K التالية (بدءًا من الرابع) على وصف لكبل واحد - ثلاثة أرقام غير سالبة عدد صحيح:
رقم المحطة الأولى ،
رقم المحطة الثانية وتكلفة التنفيذ .
تنسيق الإخراج
عدد صحيح واحد هو الحد الأدنى لتكلفة الطاقة لجميع محطات المكوك لتكوين معين.
مثال 1
مثال 2
الملاحظات
يتم ترقيم المحطات من واحدة.
يتم فصل الأرقام الموجودة داخل السطر بمسافة واحدة.
لا يلزم التحقق من صحة بيانات الإدخال.
قرار
أولاً ، يجدر الانتقال من الوصف الجميل إلى الرسم البياني الموزون غير الموجه ، حيث ستكون هناك قمم في مكان محطات المكوك ، وستصبح الكابلات حوافًا ، وستتحول تكلفة بناء الكابلات إلى أوزان الحواف المقابلة. ولكن يبقى السؤال - كيف نأخذ في الاعتبار تكلفة بناء مولدات اليورانيوم داخل المحطات (القمم) نفسها؟ الجواب على هذا السؤال هو جوهر المشكلة.
لنفترض أن هناك قمة أخرى - مصدر للطاقة ، ويتم رسم حافة من هذه القمة إلى كل من رؤوس الرسم البياني بوزن يساوي تكلفة بناء مولد يورانيوم في المحطة المقابلة (قمة الرأس). يقودنا هذا الافتراض إلى رسم بياني متصل يجب تحويله إلى شجرة بحيث يصبح مجموع أوزان الحواف فيه أصغر ما يمكن. هذا ليس أكثر من مشكلة إيجاد الحد الأدنى من شجرة الامتداد في الرسم البياني. يمكنك إنشاء شجرة تمتد على الحد الأدنى باستخدام أي من الخوارزميات المعروفة - على سبيل المثال ، بريما أو كراسكال.
رمز عينة مع التعليقات #include <algorithm> #include <iostream> #include <tuple> #include <vector> using Price = std::size_t; using Vertex = std::size_t; using Transition = std::tuple<Price, Vertex, Vertex>; using Graph = std::vector<Transition>; // ( ). class Equals { public: // . explicit Equals(std::size_t size) { equals_.resize(size); // . for (std::size_t i = 0; i < size; i++) { equals_[i] = i; } } // v1 v2 true, // . bool Emplace(std::size_t v1, std::size_t v2) { while (v1 != v2) { if (v2 < v1) { std::swap(v1, v2); } auto& next_v2 = equals_[v2]; if (next_v2 == v2) { next_v2 = v1; return true; } v2 = next_v2; } return false; } private: std::vector<size_t> equals_; }; int main() { // . std::size_t vertex_count = 0; std::cin >> vertex_count; if (vertex_count == 0) { std::cout << 0 << std::endl; return 0; } // — — . vertex_count++; // . Graph graph; graph.reserve(vertex_count); // . for (Vertex i = 1; i < vertex_count; i++) { Price price = 0; std::cin >> price; graph.emplace_back(price, 0, i); } // . std::size_t edge_count = 0; std::cin >> edge_count; for (std::size_t i = 0; i < edge_count; i++) { Price price = 0; Vertex from = 0, to = 0; std::cin >> from >> to >> price; graph.emplace_back(price, from, to); } // . std::sort(graph.begin(), graph.end()); // . // https://ru.wikipedia.org/wiki/_ Price result = 0; Equals equals{vertex_count}; for (const auto& [price, from, to] : graph) { if (equals.Emplace(from, to)) { result += price; } } // . std::cout << result << std::endl; return 0; }
لا وقوف السيارات
المؤلفون: ايليا Mescherin و Artyom Serebriyskyفي مدينة واحدة ، مُنع السيارات من التوقف ، باستثناء ركوب الركاب. والراكب لا يوافق على الانتظار أكثر من 3 دقائق. في هذه المدينة ، يطلب أحد المشاة سيارة أجرة إلى النقطة X ويشير إلى فاصل 180 ثانية. يجب أن يصل السائق بالضبط إلى هذا الفاصل الزمني. إذا وصلت قبل ذلك ، فلن تكون قادرًا على توقع وجود مسافر. إذا وصلت بعد فوات الأوان ، فسيقوم المسافر الغاضب بإلغاء الطلب.
نظرًا لهذه القيود ، بقي السائقون Z فقط في هذه المدينة ، كل منهم في بداية المهمة في أعلى الرسم البياني لحركة المرور. يجب على نظام التحكم تعيين أفضل سائق من أولئك الذين تمكنوا من الوصول إلى الفاصل الزمني المحدد. أفضل سائق هو الشخص الذي يأمر بالاقتراب من بداية الفاصل الزمني. إذا كان هناك العديد من هذه السائقين ، ثم أي منهم.
من الضروري أن يحدد كل سائق ما إذا كان لديه وقت للوصول إلى الفاصل الزمني المشار إليه ، وإذا كان الأمر كذلك ، في أي نقطة زمنية في الوقت الفاصل المشار إليه يمكنه الوصول.
وصف رسميمعين:
- الرسم البياني الموجه G مع رؤوس N وحواف K ، يتم ترقيم الرؤوس من 0 إلى N - 1 ، 0 ≤ N ≤ 10 4 ، 0 ≤ K ≤ 10 4 . كل حافة تتوافق مع وقت السفر فيها - عدد صحيح W ، 10 ≤ W ≤ 10 4 .
- موضع الطلب في العمود الهدف معرف.
- مواقف Z من السائقين في العمود IDsource 2 ، 1 ≤ Z ≤ 10 4 .
- الوقت t 0 ، 0 0 t 0 ≤ 600 هو عدد صحيح.
من الضروري لكل سائق أن يجد مثل هذه
الدقائق التي:
- يوجد مثل هذا الطريق من برنامج التشغيل IDsource z إلى هدف الهوية الذي يصل إليه السائق في t min ،
- t min ∈ [t 0 ؛ ر 0 + 180] ،
- وهذا هو أقرب وقت ممكن t min : t min ≤ t i لأي t i إرضاء النقطتين 1 و 2 ،
- أو تأكد من عدم وجود مثل هذه t min .
I / O التنسيقات والأمثلة والملاحظاتتنسيق الإدخال
يتم تعيين الرسم البياني في شكل ثلاث مرات أعلى ثلاث مرات السفر نهاية الوقت.
إدخال البيانات ، كل عنصر على السطر الخاص به:
1. K هو عدد الحواف.
2. K معرف بطاقة الهوية ثلاثية الأوزان - الرأس الأولي للضلع ، والرأس الأخير من الضلع ، ومقدار السيارة التي تقود الضلع.
3.
الهدف معرف ر
0 - أعلى الترتيب [الفضاء] بداية النطاق عندما تحتاج إلى الوصول.
4. Z - عدد السائقين.
5. (مرات Z) ID
z هو الجزء العلوي من برنامج التشغيل التالي.
تنسيق الإخراج
لكل برنامج ، بنفس الترتيب الذي دخلوا به ، اطبع على سطر منفصل t
دقيقة محسوبة أو -1 إذا لم يكن هذا t
min موجودًا.
مثال 1
مثال 2
مثال 3
الملاحظات
1. يمكن أن تنتقل عدة حواف من الرأس A إلى القمة B ، بما في ذلك الحواف التي لها نفس الوزن.
2. الأضلاع من A إلى A مسموح بها.
3. يسمح بوجود حواف (A-> B) و (B-> A) في نفس الوقت (دورات طولها 2).
قرار
سائق واحدأولاً ، سنقوم بتحليل حالة بسيطة باستخدام برنامج تشغيل واحد. إن مقياس الأضلاع هو الوقت الذي يتم فيه التعبير عن ذلك [، حيث يتم التعبير عن قيود النهاية في نفس الوحدات ، حتى نتمكن من إعادة صياغة المشكلة: "ينتقل السائق من النقطة A إلى النقطة B وفقًا للرسم البياني. ابحث عن الحد الأدنى للمسار بحيث يكمن طوله في المقطع [T ، U]. "
أسهل طريقة للقيام بذلك هي تشغيل dijkstra المعدلة من A إلى B:
- التعديل 1. افترض أننا حصلنا على القمة من minQ وأنه تم تمييزها بالفعل باللون الأسود (وهذا يعني أن الحد الأدنى للمسافة قد تم العثور عليه بالفعل). ثم لا نتجاهلها ، لكننا نعالجها بالطريقة المعتادة - ضع كل القمم المجاورة لها مع إعادة المسافة الجديدة إلى minQ.
- نوقفه فقط عندما تكون المسافة إلى قمة الرأس الحالية minQ أكبر من U.
- لنفترض أننا صادفنا قمة B أثناء النقل ، ثم إذا كانت المسافة الحالية هي ≥ T ، تذكرها كإجابة R. في هذه المرحلة ، يمكن أيضًا مقاطعة dijkstra.
وبالتالي ، إذا كان لدينا R ، فهذا هو المسار الأدنى بطول الفاصل الزمني المطلوب.
العديد من السائقينالحل للجبهة هو تشغيل خوارزمية لكل سائق. لكن مثل هذا الحل لا يمر عبر تحديد الوقت. يجب أن نتعلم إعطاء إجابة لكل برنامج تشغيل لـ O (1).
للقيام بذلك ، نقوم بتعديل الخوارزمية لبرنامج تشغيل واحد:
- بدلاً من dijkstra من برنامج التشغيل إلى نقطة الطلب ، نبدأ تشغيل dijkstra من نقطة الطلب وفقًا للرسم البياني ذي الحواف المقلوبة (!).
- نستفيد من حقيقة أن عدد القمم كان محددًا أيضًا بعشرة آلاف. دعنا نحصل على مجموعة من الإجابات R - بالنسبة لكل قمة ، يكون هذا هو الحد الأدنى من الوقت في النطاق [T ، U] عندما يمكن الوصول إليه من A.
- في عملية اجتياز الرسم البياني لـ dijkstroy المعدلة ، عندما نلتقي بالرأس j وإذا كانت المسافة الحالية إليه في الفاصل الزمني المطلوب [T ، U] ، ندخل R: R j = min (R j ، dist).
ثم ، لكل سائق في vertex J ، يمكن للمرء الاستعلام عن R
j لمعرفة ما إذا كان هناك مسار يفي بالشروط وما هو طوله.
MinQ الأمثليكون طول المسار دائمًا عددًا صحيحًا ومحدودًا من أعلى إلى 781 - بالنسبة لطلب يتم إجراؤه في t
0 = 600 ، فإن آخر ثانية صالحة من وصول السائق هي 780. في هذه الحالة ، لتنفيذ dijkstra ، تحتاج إلى استخدام التطبيق التالي لـ minQ.
لدينا مجموعة هامش من الحجم [781]. يوجد في كل عنصر من عناصر Fringe
i مجموعة غير مرتبة تخزن معرف جميع القمم التي يوجد بها مسار طول i.
1. أضف قمة ذات مسافة D:
fringe[D].insert(vertex);
2. وفقًا للشروط ، يكون الحد الأدنى لوزن الحافة> 0. لذلك ، بدلاً من أخذ عناصر من minQ واحدة في المرة الواحدة ، يمكنك المرور عبر الشريحة بأكملها:
for(int i = 0; i < fringe.size(); ++i) { if(fringe[i].empty()) { continue; } for(auto& vertex : fringe[i]) {
حاسبة تكلفة الرحلة
المؤلف: نيكولاي فيلتشنكومن الضروري حساب تكلفة السفر وفقًا للصيغة المحددة. تتميز كل رحلة بمعلمات عدد صحيح K. يتم إعطاء الصيغة في تدوين البولندية العكسي.
العمليات المسموح بها:
- + - - الجمع والطرح ؛
- * / - الضرب والعدد الصحيح.
- <= - المقارنة ؛
- ؟ المشغل الشرطي. إذا كانت الوسيطة الأولى صحيحة - تُرجع الوسيطة الثانية ، وإلا - الوسيطة الثالثة.
يتم استخدام المتغير [az] والأعداد الصحيحة من -10
9 إلى 10
9 أيضًا في الصيغة.
يمكننا أن نفترض أن نتائج جميع العمليات في الصيغة لا تتجاوز 10
9 في القيمة المطلقة. يتم استخدام نتيجة عمليات المقارنة فقط كوسيطة للمشغل الشرطي.
I / O التنسيقات والأمثلةتنسيق الإدخال
في السطر الأول ، رقم واحد 1 ≤ K ≤ 26 - عدد المتغيرات.
يحتوي السطر الثاني على صيغة لحساب السعر (لا يزيد عن 3-10 عناصر). جميع العناصر مفصولة بمسافات.
على السطر الثالث ، 1 ≤ N ≤ 10
4 هو عدد الاختبارات.
تحتوي الأسطر N التالية على أعداد صحيحة K (–10
9 ≤ v ≤ 10
9 ) - قيم المتغيرات بترتيب أبجدي.
تنسيق الإخراج
أسطر N تحتوي على عدد صحيح واحد - نتائج استبدال كل مجموعة من القيم. يتم ضمان أن تكون نتيجة التعبير محددة ومحددة
مثال 1
مثال 2
قرار
هذه مهمة للتنفيذ الدقيق والاهتمام. هناك نقطتان رئيسيتان في الحل:
- يجب تحويل التعبير الأصلي نفسه إلى مجموعة من الأرقام والعمليات حتى لا يتم تحليل السلسلة في كل مجموعة من المتغيرات.
- يجب أن نتذكر أن تقسيم عدد صحيح بمقدار صفر يؤدي إلى SIGFPE ، لذلك في عملية التقسيم ، يجدر التحقق صراحة من أن المقام ليس صفراً. استنادًا إلى ضمان الدقة واليقين لنتيجة التعبير بالكامل ، يمكننا أن نفهم: نتيجة هذه الأقسام غير متضمنة في النتيجة النهائية وفي فروع غير مشغولة مشروطة ، وبالتالي يمكنك قبولها بأيٍّ منها (على سبيل المثال ، صفر).
Habraposty على الموضوع: