الروبوتات#521

الروبوتات (Editorial)

أولاً، لاحظ أنه إذا كان كل من و فرديًا، فإن الإجابة هي "لا". نظرًا لأننا بحاجة إلى تقسيم الشبكة إلى مسارين مغلقين، ومجموع الخلايا فردي، فإن أحد المسارات يجب أن يمر عبر عدد فردي من الخلايا. إذا قمنا بتلوين جميع الخلايا بالأبيض والأسود بنمط شبيه بقطع الشطرنج، يجب أن يبدأ وينتهي أي مسار مغلق بنفس اللون. نظرًا لأنه بعد كل خطوة يتغير لون الخلية، نحتاج إلى المرور بعدد زوجي من الخلايا ليكون المسار مغلقًا. من الواضح أن الإجابة هي أيضًا "لا" للحالات التي يكون فيها min(n, m)=1، باستثناء الحالة عندما n=1; m=4 أو n=4; m=1. بقية الحالات يمكن حلها.

يمكن حل أول مهمتين يدويًا وتشفيرهما في البرنامج.

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

بالنسبة للمهمة الثالثة، يمكننا تقسيم المستطيل إلى قطعة 2 \times 1، وقطعة 2 \times m-1.

بالنسبة للمهمة الرابعة، يمكننا تقسيم المستطيل إلى قطعتين 2 \times m.

بالنسبة للمهمة الخامسة، يمكننا تقسيم المستطيل إلى قطعتين \frac{n}{2} \times m.

بالنسبة للمهمة السادسة، لم يعد بإمكاننا إجراء قطع عشوائي عبر أحد الجوانب، لأنه إذا كان إما أو فرديًا، فقد ينتهي أحد المستطيلات بوجود جانبين بطول فردي، وهو ما يستحيل حله. لذا، يجب علينا قطع مستطيلين عبر أحد الجوانب الزوجية. لتسهيل التنفيذ، من الممكن تدوير الشبكة عند الحاجة، ثم إجراء قطع عمودي وإعادتها: بهذه الطريقة لا نحتاج إلى القلق بشأن حالتين منفصلتين من القطع.

التعقيد: O(n \cdot m)