الكرات والصناديق

الكرات والصناديق

الأولمبياد الوطني للبرمجة 2026 - المسابقة الثالثة

الزمن المحدد: 0.5 ثانية
الذاكرة المحددة: 256 ميجابايت

يوجد \(3\) صناديق تحتوي على كرات من \(3\) ألوان مختلفة.
لكل صندوق، أنت تعرف عدد الكرات من كل لون الموجودة داخله.

هدفك هو نقل أقل عدد ممكن من الكرات من صندوق إلى آخر، بحيث بعد انتهاء جميع النقلات:

• لا توجد كرتان في نفس الصندوق بلونين مختلفين.
• لا توجد كرتان في صندوقين مختلفين ولهما نفس اللون.

رسم توضيحي للكرات والصناديق

المدخلات

التوزيع الابتدائي للكرات داخل الصناديق يُعطى على شكل مصفوفة \(3 \times 3\) اسمها \(A\)، حيث إن \(A_{i,j}\) يمثل عدد الكرات من اللون \(i\) الموجودة في الصندوق \(j\)، و\(0 \le A_{i,j} \le 100\).

تتكون المدخلات من ثلاثة أسطر: \(A_{1,1}\ A_{1,2}\ A_{1,3}\)، ثم \(A_{2,1}\ A_{2,2}\ A_{2,3}\)، ثم \(A_{3,1}\ A_{3,2}\ A_{3,3}\).

المخرجات

اطبع عددًا صحيحًا واحدًا: أقل عدد من الكرات التي يجب نقلها.

التقييم

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

• في \(30\%\) من حالات الاختبار، يكون الصندوق الثالث فارغًا.
• في \(30\%\) أخرى من حالات الاختبار، يكون الصندوقان الثاني والثالث فارغين.

أمثلة

المدخلات

2 0 0
3 0 0
0 0 0

المخرجات

2

المدخلات

3 1 0
9 5 0
0 0 0

المخرجات

8

المدخلات

3 1 7
6 6 8
2 4 5

المخرجات

25

الملاحظات

شرح المثال الأول:
في الصندوق الأول توجد \(2\) كرات من اللون الأول و \(3\) كرات من اللون الثاني. الصندوقان الآخران فارغان. إذا نقلنا \(2\) كرات من اللون الأول إلى الصندوق الثاني، نكون قد حققنا الهدف. لا يمكن تحقيق ذلك بعدد أقل من النقلات، لذلك الإجابة هي \(2\).

شرح المثال الثاني:
الحل الأمثل هو نقل \(3\) كرات من اللون الأول من الصندوق الأول إلى الصندوق الثاني، ونقل \(5\) كرات من اللون الثاني من الصندوق الثاني إلى الصندوق الأول.

المثال الثالث موضح في الصورة.

الحل

في الترتيب النهائي يجب أن يشغل كل لون صندوقًا مختلفًا. لا يوجد إلا \(3!=6\) إسنادات للألوان إلى الصناديق. في كل إسناد لا تتحرك الكرات الموجودة أصلًا في صناديقها المطلوبة، وتتحرك البقية. عظّم عدد الكرات التي تبقى مكانها، ثم اطرحه من العدد الكلي. التعقيد \(O(1)\).

#include <algorithm>
#include <iostream>
using namespace std;

int main() {
    int a[3][3];
    int total = 0;

    for (int colour = 0; colour < 3; colour++) {
        for (int box = 0; box < 3; box++) {
            cin >> a[colour][box];
            total += a[colour][box];
        }
    }

    int boxes[3] = {0, 1, 2};
    int mostKept = 0;

    do {
        int kept = 0;
        for (int colour = 0; colour < 3; colour++) {
            kept += a[colour][boxes[colour]];
        }
        mostKept = max(mostKept, kept);
    } while (next_permutation(boxes, boxes + 3));

    cout << total - mostKept << '\n';
}