الثلاثي المثالي

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

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

يلعب ثلاثة أصدقاء لعبة تنسيق اسمها «الثلاثي المثالي».

أُعطوا قائمة مشاهير؛ لدى المشهور رقم \(i\) بالضبط \(A_i\) متابعًا. للفوز يجب اختيار ثلاثة مشاهير مختلفين بالضبط، بحيث يساوي مجموع أعداد متابعيهم \(S\).

حدد هل يوجد هذا الثلاثي. إذا وُجد فاطبع أي ثلاث قيم صحيحة، وإلا فاطبع \(-1\).

المدخلات

يحتوي السطر الأول على \(N\) و\(S\)، عدد المشاهير والمجموع المطلوب. ويحتوي السطر الثاني على \(N\) عددًا \(A_1,A_2,\ldots,A_N\).

مضمون أن \(3 \le N \le 10000\) و\(0 \le A_i,S \le 7\cdot10^8\).

المخرجات

إذا وُجد ثلاثة مشاهير مختلفون مجموع متابعيهم \(S\)، فاطبع أي ثلاث قيم منهم. وإلا فاطبع \(-1\).

التقييم

المهمة الفرعية القيود الإضافية النقاط
\(1\) \(N=3\) \(7\)
\(2\) \(N=4\) \(8\)
\(3\) \(N=5\) \(9\)
\(4\) \(N\le100\) \(26\)
\(5\) \(N\le10000, S\le100000\) \(31\)
\(6\) \(N\le10000, S\le7\cdot10^8\) \(19\)

أمثلة

المدخلات

3 6
1 2 3

المخرجات

1 2 3

المدخلات

6 1000
182 587 952 374 39 741

المخرجات

39 374 587

ملاحظات

في المثال، القيم الثلاث المختارة لأعداد المتابعين هي \(374\) و\(39\) و\(587\)، ومجموعها:

\[374 + 39 + 587 = 1000\]

لاحظ أن:

  • المشاهير الثلاثة المختارون يجب أن يكونوا مختلفين؛
  • إذا وُجدت عدة إجابات صحيحة، فيمكنك طباعة أي واحدة منها؛
  • يمكن طباعة القيم بأي ترتيب.
الحل

رتّب أعداد المتابعين. ثبّت المشهور الأول عند الموضع \(i\)، ثم استخدم مؤشرين للبحث عن قيمتين لاحقتين مجموعهما \(S-A_i\). حرّك المؤشر الأيسر يمينًا إذا كان المجموع أصغر من المطلوب، والأيمن يسارًا إذا كان أكبر. المواضع الثلاثة مختلفة دائمًا حتى لو تساوت بعض القيم. التعقيد \(O(N^2)\) زمنيًا و\(O(1)\) ذاكرة إضافية عدا المصفوفة المرتبة.

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

int main() {
    int n;
    long long target;
    cin >> n >> target;

    vector<long long> a(n);
    for (long long& value : a) {
        cin >> value;
    }
    sort(a.begin(), a.end());

    for (int i = 0; i < n - 2; i++) {
        int left = i + 1;
        int right = n - 1;

        while (left < right) {
            long long sum = a[i] + a[left] + a[right];
            if (sum == target) {
                cout << a[i] << ' ' << a[left] << ' ' << a[right] << '\n';
                return 0;
            }
            if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
    }

    cout << -1 << '\n';
}