Domino piling
توجد مصفوفة ثنائية الأبعاد مكوّنة من \(N\) صف و \(M\) عمود. لديك عدد غير محدود من القطع ذات الحجم 2 × 1، وتريد وضع أكبر عدد ممكن من هذه القطع في المصفوفة بحيث:
- كل قطعة تغطي خانين كاملين.
- جميع القطع لا تتقاطع.
- جميع القطع تكون داخل المصفوفة بشكل كامل.
Solution
في هذه المسألة لدينا 3 حالات. لنحللها:
\(N\) عدد زوجي (
N % 2 == 0):
يمكننا تغطية المصفوفة كاملة بوضع القطع بشكل عمودي.
عدد القطع المستخدمة سيكون
\[ \frac{N \times M}{2} \]
لأن المصفوفة تحتوي على \(N \times M\) خانة وكل قطعة تغطي خانتين.\(M\) عدد زوجي (
M % 2 == 0):
يمكننا تغطية المصفوفة كاملة بوضع القطع بشكل أفقي.
عدد القطع سيكون
\[ \frac{N \times M}{2} \]كلا من \(N\) و \(M\) عددان فرديان (
N % 2 == 1وM % 2 == 1):
أولًا، نضع القطع بشكل عمودي ابتداء من الصف الأول، مما يترك صفًا كاملًا غير مغطى (لأن \(N\) فردي).
في ذلك الصف نضع القطع بشكل أفقي، فتتبقى خانة واحدة فقط غير مغطاة (لأن \(M\) فردي).
بالتالي عدد القطع المستخدمة سيكون
\[ \frac{N \times M - 1}{2} \]
#include <iostream>
using namespace std;
int main() {
int N, M;
cin >> N >> M;
if (N % 2 == 0) {
cout << (N * M) / 2 << endl;
}
else if (M % 2 == 0) {
cout << (N * M) / 2 << endl;
}
else {
cout << (N * M - 1) / 2 << endl;
}
}