Permutations

Permutations

CSES easy

يكون تبديل الأعداد \(1, 2, \ldots, n\) جميلًا إذا لم يكن الفرق بين أي عنصرين متجاورين فيه \(1\).

أنشئ تبديلًا جميلًا، أو بيّن أنه لا يوجد.

القيود:

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

الإدخال:

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

المخرجات:

• تبديل جميل للأعداد \(1, 2, \ldots, n\). إذا وُجد أكثر من تبديل فاطبع أيًّا منها. إذا لم يوجد فاطبع NO SOLUTION.

أمثلة:

الإدخال:

5

المخرجات:

4 2 5 3 1

الإدخال:

3

المخرجات:

NO SOLUTION

الحل

نبدأ بقيم \(n\) الصغيرة، كما يقترح درس الخوارزميات البنائية:

• \(n = 1\): التبديل \(1\) ليس فيه عناصر متجاورة، فهو جميل.
• \(n = 2\) و \(n = 3\): يمكننا فحص كل الترتيبات؛ في كل منها يجاور \(2\) العدد \(1\) أو العدد \(3\). لا يوجد حل.
• \(n = 4\): التبديل \(2\ 4\ 1\ 3\) جميل.

فكرة \(2\ 4\ 1\ 3\) تصلح لكل \(n \ge 4\): نطبع أولًا كل الأعداد الزوجية بترتيب تصاعدي، ثم كل الأعداد الفردية بترتيب تصاعدي.

• الفرق بين عددين زوجيين متجاورين \(2\)، وكذلك بين عددين فرديين متجاورين.
• عند الحد الفاصل يجاور أكبر عدد زوجي العدد \(1\). هذا العدد الزوجي لا يقل عن \(4\)، لذلك لا يقل الفرق عن \(3\).

عندما \(n = 1\) لا يطبع البرنامج نفسه أي عدد زوجي ثم يطبع العدد \(1\)، وهذا صحيح أيضًا.

#include <iostream>
using namespace std;

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

    if (n == 2 || n == 3) {
        cout << "NO SOLUTION\n";
        return 0;
    }

    // first all even numbers, then all odd numbers
    for (int i = 2; i <= n; i += 2) {
        cout << i << ' ';
    }
    for (int i = 1; i <= n; i += 2) {
        cout << i << ' ';
    }
    cout << "\n";
}