Permutations
Permutations
A permutation of the numbers \(1, 2, \ldots, n\) is beautiful if no two adjacent elements differ by \(1\).
Construct a beautiful permutation, or report that none exists.
Constraints:
- \(1 \le n \le 10^6\)
Input:
- One line: integer \(n\).
Output:
- A beautiful permutation of \(1, 2, \ldots, n\). If there are several, print any of them. If there is none, print
NO SOLUTION.
Examples:
Input:
5
Output:
4 2 5 3 1
Input:
3
Output:
NO SOLUTION
Solution
We start with small \(n\), as the lesson on constructive algorithms suggests:
- \(n = 1\): the permutation \(1\) has no adjacent elements, so it is beautiful.
- \(n = 2\) and \(n = 3\): we can check all orders; in each of them \(2\) is next to \(1\) or to \(3\). There is no solution.
- \(n = 4\): \(2\ 4\ 1\ 3\) is beautiful.
The idea of \(2\ 4\ 1\ 3\) works for every \(n \ge 4\): first print all even numbers in increasing order, then all odd numbers in increasing order.
- Two adjacent even numbers differ by \(2\), and so do two adjacent odd numbers.
- At the border, the largest even number is next to \(1\). It is at least \(4\), so the difference is at least \(3\).
For \(n = 1\) the same code prints no even numbers and then the number \(1\), which is also correct.
#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";
}