الوليمة
الزمن المحدد: 1 ثانية الذاكرة المحددة: 256 ميجابايت
في قاعة مُعدّة لوليمة، يمكن لكل متر مربع من الأرضية أن يحتوي إما على طاولة مربعة واحدة أو كرسي واحد. حول كل طاولة مربعة، يمكن وضع ما لا يزيد عن \(8\) كراسٍ: كرسي واحد بمحاذاة كل ضلع، وكرسي واحد عند كل زاوية.
اكتب برنامجًا يحسب أكبر عدد ممكن من الكراسي التي يمكن وضعها في القاعة، مع افتراض أن كل كرسي يجب أن يكون مجاورًا لطاولة واحدة على الأقل.
المدخلات
يحتوي السطر الوحيد من المدخلات القياسية على عددين صحيحين \(R\) و\(K\)، حيث \(1 \le R, K \le 1000\). ويمثلان طول قاعة الوليمة وعرضها بالأمتار، ويفصل بينهما فراغ.
المخرجات
اطبع عددًا صحيحًا واحدًا: أكبر عدد ممكن من الكراسي التي يمكن وضعها في قاعة الوليمة.
التقييم
| المهمة الفرعية | قيود إضافية | النقاط |
|---|---|---|
| \(1\) | \(R, K \le 5\) | \(8\) |
| \(2\) | \(\min(R, K) = 1\) | \(10\) |
| \(3\) | \(\min(R, K) \le 2\) | \(14\) |
| \(4\) | \(R \bmod 3 = 0\) و\(K \bmod 3 = 0\) | \(16\) |
| \(5\) | واحد على الأقل من \(R\) و\(K\) يقبل القسمة على \(3\) | \(20\) |
| \(6\) | لا توجد قيود إضافية | \(32\) |
أمثلة
المدخلات
3 4المخرجات
10الملاحظات
الشرح: تحتوي القاعة على \(3 \times 4 = 12\) مترًا مربعًا.
يمكننا وضع \(2\) طاولتين واستخدام المربعات المتبقية وعددها \(10\) للكراسي. على سبيل المثال:
C C C C
C T C T
C C C Cهنا، يمثل الرمز T طاولة، ويمثل الرمز C كرسيًا.
كل كرسي موضوع بجوار طاولة واحدة على الأقل، إما من جهة ضلع أو من جهة زاوية. وبما أن الطاولة الواحدة يمكن أن يكون حولها ما لا يزيد عن \(8\) كراسٍ، فإن وضع طاولة واحدة فقط لن يكون كافيًا لـ \(11\) كرسيًا. لذلك، فإن أكبر عدد ممكن من الكراسي هو \(10\).
الحل
تغطي الطاولة مربعها والمربعات الثمانية المجاورة، أي كتلة \(3\times3\). لذلك نحتاج على الأقل \(\lceil R/3\rceil\cdot\lceil K/3\rceil\) طاولة، ويمكن تحقيق هذا الحد بوضع طاولة في كل مجموعة من ثلاثة صفوف وثلاثة أعمدة. يمكن وضع كراسٍ في بقية المربعات، لذا اطرح أقل عدد من الطاولات من مساحة القاعة. التعقيد \(O(1)\).
#include <iostream>
using namespace std;
int main() {
long long rows, columns;
cin >> rows >> columns;
long long tables = (rows + 2) / 3 * ((columns + 2) / 3);
cout << rows * columns - tables << '\n';
}