البرمجة التنافسية

هيدا المقال رح يكون بداية لسلسلة جديدة رح نحكي فيها عن البرمجة التنافسية Competitive programmingو أهم الخورازميات المستخدمة فيها ورح تكون هالسلسلة مرجع لأي شخص حابب يدخل بهالمجال و يشارك بالمسابقات البرمجية أو ببساطة حابب يطور حالو و يتعلم شي جديد.

ماهي البرمجة التنافسية؟

البرمجةالتنافسية هي حل مسائل معرفة بشكل جيد عن طريق كتابة برامج حسوبية تعمل ضمن القيود المحددة.

أي أننا نقوم بحل مسائل لها حل وعلى الأقل قام كاتب المسألة بحلها ولا نبحث عن حلول لمسائل ومشكلات غير معروفة.

بناء على التعريف السابق البرمجة التنافسية لديها ثلاث عناصر أساسية :

1-  مسألة معرفة جيداً: في البرمجة التنافسية سوف تواجه مسألة أو أكثر، نص المسألة يحوي متغيرات، يجب أن تكون قادراً على حل المسألة وإعطاء الخرج الصحيح بناء على أي تركيبة معطاة من تركيبات الدخل، المسألة يجب أن تكون معرفة بشكل واضح وسوف يتم تحديد كافة القيود المفروضة وإعطاءك الملاحظات الضرورية.

2-  برنامج حاسوبي: سوف تكتب برنامج حاسوبي يحل المسألة المعطاة حيث يكون هذا البرنامج عبارة عن برنامج يعمل ضمن بيئة سطر الأوامر( command line ) من دون استخدام ال GUI  ، البرنامج يقوم بقراءة الدخل المطلوب من الدخل القياسي ويجب أن يكتب النتيجة في الخرج القياسي.

3-  القيود المحددة: البرنامج يجب أن يعمل ويعطي الخرج الصحيح ضمن قيود الزمن والحجم المحددة كما أنه يجب عليك كتابة البرنامج بواسطة واحدة من لغات البرمجة المحددة أيضاً.

خصائص المسألة:

مسألة برمجة تنافسية غالبا مايكون لديها الخصائص التالية:
1- حل المسألة يجب أن يكون صحيح بشكل مطلق: فالإجابات يتم فحصها بواسطة الحواسيب وليس بواسطة البشر ولا يوجد مجال لأي معاملة شخصية، الحل يجب أن يكون إما صحيح أو خاطئ.
2- الوصف يحتوي قصة تختفي المسألة الحقيقية ضمنها وتجعلها مثيرة للاهتمام.
3- يوجد بعض الأمثلة لدخل و خرج المسألة وبذلك لايمكننا أن نسيئ فهم صيغ الدخل والخرج المطلوبة وحتى نص المسألة بحد ذاته.
4- وفي نهاية المطاف المسألة تكون متعلقة ب علوم الحاسب أو الرياضيات أو المنطق وبذلك يعبر عن الحل بواسطة خوارزمية ضمن برنامج حاسوبي.

قواعد إحتساب الحل والنقاط :

يقوم الحكام بإضافة مجموعة من حالات الاختبار. كل حالة إختبار تتألف من دخل صحيح والخرج الصحيح الموافق لهذا الدخل، ملفات الدخل والخرج يجب أن توافق صيغ الدخل والخرج والقيود المحددة ضمن نص التعليمة، ويجتاز برنامج المتسابق حالة الإختبار عندما يعطي خرج موافق ل خرج حالة الختبار المطبق دخلها عليه.رصيد المسألة يعتمد على قواعد المسابقة، في بعض المسابقات البرنامج يجب أن يجتاز جميع حالات الإختبار لكسب نقاط المسألة، بينما في مسابقات أخرى تنال نقاط جزئية معتمدة على عدد حالات الإختبار التي إجتازها برنامجك.