Two Sets

Two Sets

CSES medium

قسّم الأعداد \(1, 2, \ldots, n\) إلى مجموعتين مجموعاهما متساويان.

القيود:

• \(1 \le n \le 10^6\)

الإدخال:

• سطر واحد: عدد صحيح \(n\).

المخرجات:

• YES إذا كان التقسيم ممكنًا، وإلا NO.
• إذا كان ممكنًا، فصِف المجموعتين: لكل مجموعة سطر فيه عدد عناصرها، وسطر فيه عناصرها.

أمثلة:

الإدخال:

7

المخرجات:

YES
4
1 2 4 7
3
3 5 6

الإدخال:

6

المخرجات:

NO

الحل

مجموع كل الأعداد هو \(S = n(n + 1) / 2\). إذا كان \(S\) فرديًا فلا يمكن تقسيمه إلى نصفين صحيحين متساويين، فالجواب NO.

إذا كان \(S\) زوجيًا فالتقسيم موجود دائمًا، ونحن ننشئه. يجب أن يكون مجموع المجموعة الأولى \(T = S / 2\). نمر على الأعداد من \(n\) نزولًا إلى \(1\)، ونضع العدد \(i\) في المجموعة الأولى إذا كان \(i \le T\)، حيث \(T\) هو المجموع الذي ما زالت المجموعة الأولى تحتاجه. وإلا يذهب \(i\) إلى المجموعة الثانية.

لماذا يصبح مجموع المجموعة الأولى \(S / 2\) بالضبط؟ لا يمكن أن تأخذ المجموعة الأولى كل الأعداد، لأن مجموعها \(S\) أكبر من \(S / 2\). إذن يُترك عدد ما. لنأخذ أول عدد \(i\) يُترك لأن \(i > T\). عندها \(T \le i - 1\)، والعدد \(T\) نفسه ما زال بين الأعداد غير المستعملة \(1, \ldots, i - 1\). من هذه اللحظة يُترك كل عدد أكبر من \(T\)، وعندما تصل الحلقة إلى العدد \(T\) تأخذه فيصبح \(T\) مساويًا للصفر.

عندما \(n = 7\): \(S = 28\) و \(T = 14\). نأخذ \(7\) و \(6\) (فيصبح \(T = 1\))، ونترك \(5, 4, 3, 2\)، ونأخذ \(1\). المجموعتان \(\{7, 6, 1\}\) و \(\{5, 4, 3, 2\}\)، ومجموع كل منهما \(14\).

قد يبلغ \(S\) نحو \(5 \cdot 10^{11}\)، لذلك نخزّنه في long long.

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

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

    long long sum = 1LL * n * (n + 1) / 2;
    if (sum % 2 == 1) {
        cout << "NO\n";
        return 0;
    }

    long long target = sum / 2;  // the sum that the first set still needs
    vector<int> first, second;

    for (int i = n; i >= 1; i--) {
        if (i <= target) {
            first.push_back(i);
            target -= i;
        } else {
            second.push_back(i);
        }
    }

    cout << "YES\n";
    cout << first.size() << "\n";
    for (int x : first) {
        cout << x << ' ';
    }
    cout << "\n";
    cout << second.size() << "\n";
    for (int x : second) {
        cout << x << ' ';
    }
    cout << "\n";
}