أزواج AND

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

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

أُعطيت \(n\) عددًا صحيحًا \(a_1, a_2, \dots, a_n\).

أوجد أكبر قيمة ممكنة لـ \(a_i ~\&~ a_j\) بين جميع الأزواج ذات الفهارس المختلفة \(i \ne j\).

هنا، الرمز \(\&\) يدل على عملية AND على مستوى البتات.

عملية AND على مستوى البتات تقارن عددين بتًا بتًا. لكل موضع بت:

  • إذا كان كلا البتين يساويان \(1\)، فإن البت الناتج يساوي \(1\).
  • غير ذلك، فإن البت الناتج يساوي \(0\).

على سبيل المثال، \(10 = (1010)_2\) و\(15 = (1111)_2\)، لذلك \(10 ~\&~ 15 = (1010)_2 = 10\).

المدخلات

يحتوي السطر الأول على عدد صحيح واحد \(n\)، حيث \(2 \le n \le 10^5\).

يحتوي السطر الثاني على \(n\) أعداد صحيحة \(a_1, a_2, \dots, a_n\)، حيث \(0 \le a_i < 2^{30}\).

المخرجات

اطبع عددًا صحيحًا واحدًا: أكبر قيمة ممكنة لـ \(a_i ~\&~ a_j\) بين جميع الأزواج ذات الفهارس المختلفة.

التقييم

المجموعة قيود إضافية النقاط
1 جميع الأعداد متساوية 4
2 \(n \le 1000\) 7
3 \(n \le 7000\) 10
4 \(a_i \le 1023\) 12
5 جميع الأعداد على الصورة \(2^k - 1\)، وقد تختلف قيمة \(k\) بين الأعداد 14
6 يوجد بالضبط عددان تكون قيمة البت رقم \(29\) فيهما مساوية لـ \(1\)، وهذا هو أكبر بت ممكن 15
7 يوجد على الأكثر \(1000\) قيمة مختلفة 17
8 لا توجد قيود إضافية 21

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

أمثلة

المدخلات

5
10 6 15 3 8

المخرجات

10

الملاحظات

عملية AND على مستوى البتات تبقي فقط البتات التي تساوي \(1\) في كلا العددين.

في المثال، الأعداد بالتمثيل الثنائي هي: \(10 = (1010)_2\)، و\(6 = (0110)_2\)، و\(15 = (1111)_2\)، و\(3 = (0011)_2\)، و\(8 = (1000)_2\).

الآن نفحص جميع الأزواج:

  • \(10 ~\&~ 6 = 2\)، لأن \((1010)_2 ~\&~ (0110)_2 = (0010)_2\).
  • \(10 ~\&~ 15 = 10\)، لأن \((1010)_2 ~\&~ (1111)_2 = (1010)_2\).
  • \(10 ~\&~ 3 = 2\)، لأن \((1010)_2 ~\&~ (0011)_2 = (0010)_2\).
  • \(10 ~\&~ 8 = 8\)، لأن \((1010)_2 ~\&~ (1000)_2 = (1000)_2\).
  • \(6 ~\&~ 15 = 6\)، لأن \((0110)_2 ~\&~ (1111)_2 = (0110)_2\).
  • \(6 ~\&~ 3 = 2\)، لأن \((0110)_2 ~\&~ (0011)_2 = (0010)_2\).
  • \(6 ~\&~ 8 = 0\)، لأن \((0110)_2 ~\&~ (1000)_2 = (0000)_2\).
  • \(15 ~\&~ 3 = 3\)، لأن \((1111)_2 ~\&~ (0011)_2 = (0011)_2\).
  • \(15 ~\&~ 8 = 8\)، لأن \((1111)_2 ~\&~ (1000)_2 = (1000)_2\).
  • \(3 ~\&~ 8 = 0\)، لأن \((0011)_2 ~\&~ (1000)_2 = (0000)_2\).

أكبر قيمة بين هذه القيم هي \(10\)، وتتحقق باستخدام الزوج \((10, 15)\).

الحل

ابنِ الإجابة من أعلى بت إلى أدناه. أضف البت الحالي مؤقتًا إلى قناع الإجابة، ثم احسب عدد القيم التي تحتوي كل بتات القناع. إذا كان العدد اثنين على الأقل، فهناك قيمتان يحتوي ناتج AND بينهما القناع كله، لذا أبقِ البت؛ وإلا فاحذفه. التعقيد \(O(30N)\) زمنيًا و\(O(N)\) للذاكرة.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> a(n);
    for (int& value : a) {
        cin >> value;
    }

    int answer = 0;

    for (int bit = 29; bit >= 0; bit--) {
        int candidate = answer | (1 << bit);
        int count = 0;

        for (int value : a) {
            if ((value & candidate) == candidate) {
                count++;
            }
        }

        if (count >= 2) {
            answer = candidate;
        }
    }

    cout << answer << '\n';
}