Solución

Necesitamos acomodar los números del 1 al N de tal forma que ningún par de números consecutivos en el arreglo tenga diferencia absoluta 1.

Es decir, si tenemos dos personas sentadas juntas a y b, debe cumplirse:

\[ |a-b| \neq 1 \]

Observación

Una forma sencilla de construir el arreglo es separar los números pares de los impares.

Primero colocamos todos los números pares:

\[ 2,\ 4,\ 6,\ 8,\ \ldots \]

y después todos los números impares:

\[ 1,\ 3,\ 5,\ 7,\ \ldots \]

Dentro de cada grupo, la diferencia entre dos números consecutivos es 2, por lo que nunca tendremos dos amigos que se parezcan.

El único problema puede aparecer en la unión entre los pares y los impares.

Por ejemplo, para N = 10:

2 4 6 8 10 | 1 3 5 7 9

La diferencia entre 10 y 1 es 9, así que tampoco hay problema.

Sin embargo, para algunos valores pequeños de N no existe solución.

Podemos verificar:

• N = 2: 1 2 → imposible.
• N = 3: cualquier permutación termina teniendo dos números consecutivos juntos → imposible.
• N = 4: 2 4 1 3 → válido.
• Para N >= 4, la construcción de pares seguidos de impares funciona.

Por lo tanto:

\[ \boxed{N < 4 \Rightarrow \text{NO SOLUTION}} \]

y para N >= 4:

\[ \boxed{\text{pares} + \text{impares}} \]

Ejemplo

Para N = 10:

2 4 6 8 10 1 3 5 7 9

Comprobamos las diferencias:

|2 - 4| = 2
|4 - 6| = 2
|6 - 8| = 2
|8 - 10| = 2
|10 - 1| = 9
|1 - 3| = 2
|3 - 5| = 2
|5 - 7| = 2
|7 - 9| = 2

Ninguna es 1, así que el acomodo es válido.

Complejidad

Tenemos que imprimir N números, por lo que:

• Tiempo: O(N)
• Memoria: O(1) adicional.

Código en C++

#include <bits/stdc++.h>
using namespace std;

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

    int N;
    cin >> N;

    if (N < 4) {
        cout << "NO SOLUTION\n";
        return 0;
    }

    bool first = true;

    // Números pares
    for (int i = 2; i <= N; i += 2) {
        if (!first) cout << ' ';
        cout << i;
        first = false;
    }

    // Números impares
    for (int i = 1; i <= N; i += 2) {
        cout << ' ' << i;
    }

    cout << '\n';

    return 0;
}

¿Por qué funciona?

Los pares consecutivos siempre difieren en 2:

\[ |2k-(2k+2)|=2 \]

y lo mismo ocurre con los impares:

\[ |(2k+1)-(2k+3)|=2 \]

Además, al pasar del último par al primer impar, para N >= 4 la diferencia tampoco es 1.

Por eso ningún par de personas sentadas juntas tendrá números cuya diferencia absoluta sea 1.