Domino Piling
تم إعطاؤك لوحة بحجم \(M \times N\) ودومينو \(2\times1\) غير محدود (يمكن تدويره). ضع أكبر عدد ممكن من الدومينو بحيث تقع بالكامل ضمن اللوحة ولا تتداخل مع بعضها. اطبع الحد الأقصى لعدد الدومينو.
Solution
كل دومينو يغطي خانتين بالضبط، لذا لا يمكن لأي ترتيب أن يستخدم أكثر من \(\left\lfloor \dfrac{MN}{2} \right\rfloor\) دومينو.
برهان باستخدام رقعة الشطرنج (الحد الأعلى). لون اللوحة \(M\times N\) مثل رقعة الشطرنج، ولتكن \(B\) و \(W\) مجموعات الخانات السوداء والبيضاء. كل دومينو \(2\times1\) يغطي دائمًا خانة سوداء وأخرى بيضاء، لذا أي ترتيب يستخدم على الأكثر \(\min\bigl(\lvert B\rvert,\lvert W\rvert\bigr)\). إذا كان \(MN\) زوجيًا، فإن \(\lvert B\rvert=\lvert W\rvert=MN/2\)؛ وإذا كان \(MN\) فرديًا، يختلفان بمقدار 1. لذلك: \(\max \text{ دومينو } \le \left\lfloor \dfrac{MN}{2} \right\rfloor\).
إمكانية التنفيذ (بناء صريح).
- إذا كان أحد \(M\) أو \(N\) زوجيًا: غطّ اللوحة بالكامل (تحصل على \(MN/2\) دومينو).
- إذا كان كلا \(M\) و \(N\) فرديًا: املأ كل الخانات ما عدا واحدة، فتحصل على \(\dfrac{MN-1}{2}\) دومينو.
لذلك، في جميع الحالات الحد الأقصى يساوي \(\left\lfloor \dfrac{MN}{2} \right\rfloor\).
بالنسبة للأعداد الصحيحة، \(\left\lfloor \dfrac{MN}{2}\right\rfloor\) يمكن كتابته ببساطة كـ (M*N)/2 باستخدام القسمة الصحيحة.
#include <iostream>
using namespace std;
int main() {
long long M, N;
cin >> M >> N;
cout << (M * N) / 2; // floor(M*N/2)
}على الرغم من أن \(1 \le M \le N \le 16\)، لذا استخدام int آمن، إلا أن استخدام long long (كما في الأعلى) عادة جيدة لمشاكل مماثلة لتجنب تجاوز السعة عند زيادة حاصل الضرب.