Sum of Three Values

Sum of Three Values
CSES medium

يُعطى لك مصفوفة من \(n\) أعداد صحيحة، ومهمتك هي إيجاد ثلاث قيم في مواقع مختلفة يكون مجموعها \(x\).

الإدخال:

  • السطر الأول: عددان صحيحان \(n\) و \(x\) — حجم المصفوفة والمجموع المطلوب.
  • السطر الثاني: \(n\) عددًا \(a_1,a_2,\dots,a_n\) — قيم المصفوفة.

المخرجات:

اطبع ثلاثة أعداد صحيحة: مواقع القيم المختارة (مرقّمة من 1). إذا كان هناك أكثر من ثلاثية صالحة، يمكنك طباعة أي منها. إذا لم توجد أي ثلاثية تحقق الشرط، فاطبع

IMPOSSIBLE

القيود:

  • \(1 \le n \le 5000\)
  • \(1 \le x, a_i \le 10^9\)

مثال:

الإدخال:

4 8
2 7 5 1

المخرجات:

1 3 4

Solution

نريد إيجاد ثلاثة مؤشرات مختلفة \(i, j, k\) بحيث a_i + a_j + a_k = x.

الحل العنيف بالكامل يفحص جميع الثلاثيات في زمن \(O(n^3)\)، وهذا أبطأ من اللازم عندما يكون \(n = 5000\).

بدلًا من ذلك نستخدم الفكرة الكلاسيكية:

نُثبّت عنصرين ونبحث عن الثالث باستخدام البحث الثنائي.

1. الفرز مع الاحتفاظ بالمواقع الأصلية

أولًا نخزن كل عنصر مع موقعه الأصلي، ثم نفرز حسب القيمة:

  • نبني مصفوفة أزواج: \((a_i, i)\).
  • نفرز حسب \(a_i\).

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

2. تثبيت عنصرين والبحث الثنائي عن الثالث

بعد الفرز:

  • نكرّر على جميع الأزواج \((i, j)\) بحيث \(0 \le i < j < n\):

    • نحسب need = x - a_i - a_j.
    • نريد الآن أن نرى هل يوجد \(k > j\) بحيث \(a_k = \text{need}\).
    • بما أن المصفوفة مرتّبة، يمكننا استخدام البحث الثنائي عن need في المجال [j+1, n-1].

إذا وجدنا مثل هذا k:

  • نطبع المواقع الأصلية لـ \(a_i, a_j, a_k\).

إذا أنهينا كل الأزواج بدون نجاح، نطبع IMPOSSIBLE.

بما أننا نبحث دائمًا فقط في مواقع أكبر من j، فإن المواقع الثلاثة ستكون مختلفة تلقائيًا.

3. التعقيد

  • الفرز: \(O(n \log n)\)
  • الحلقة المزدوجة على \((i, j)\): عددها \(O(n^2)\)
  • لكل زوج، بحث ثنائي واحد: \(O(\log n)\)

إذًا الزمن الكلي:

O(n^2 log n)

وهو مناسب تمامًا لـ \(n \le 5000\). استخدام الذاكرة هو \(O(n)\) لتخزين مصفوفة الأزواج.

Noteملاحظة: مخطط الخوارزمية

  1. نقرأ \(n\)، \(x\)، والمصفوفة.

  2. نبني vector<(value, original_index)> ونفرزه حسب القيمة.

  3. لكل i من 0 حتى n-1:

    • ولكل j من i+1 حتى n-1:

      • نحسب need = x - value[i] - value[j].
      • نبحث ثنائيًا عن need في المجال [j+1, n-1].
      • إذا وجدناه عند k، نطبع المؤشرات الأصلية الثلاثة وننهي البرنامج.

  4. إذا لم نجد أي ثلاثية، نطبع IMPOSSIBLE.

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

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

    int n;
    long long x;
    cin >> n >> x;

    vector<pair<long long,int>> a(n);
    for (int i = 0; i < n; ++i) {
        long long v;
        cin >> v;
        a[i] = {v, i + 1}; // store value and original 1-based index
    }

    sort(a.begin(), a.end()); // sort by value

    // Fix two indices (i, j) and binary search for the third
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            long long need = x - a[i].first - a[j].first;

            int lo = j + 1, hi = n - 1;
            while (lo <= hi) {
                int mid = (lo + hi) / 2;
                if (a[mid].first == need) {
                    // Found a valid triple
                    cout << a[i].second << " "
                         << a[j].second << " "
                         << a[mid].second << "\n";
                    return 0;
                } else if (a[mid].first < need) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
        }
    }

    cout << "IMPOSSIBLE\n";
    return 0;
}
Cautionحذر: نوع المتغيّرات
  • استخدم long long للقيم ولـ x، لأن \(x\) و \(a_i\) قد يصلان إلى \(10^9\)، والمجموع قد يصل إلى \(3 \cdot 10^9\).
  • تأكّد دائمًا من أن البحث يكون في المجال [j+1, n-1] لضمان أن المواقع الثلاثة مختلفة.