eolymp
bolt
Try our new interface for solving problems
Problems

Fuad’s challenge

Fuad’s challenge

\includegraphics{https://eolympusercontent.com/images/67etuei7ft6sjbf02jlcibphbc.gif} With the launch of the “Technest” Scholarship Program in 2023 at the International Olympiad training camp, after hard trainings Fuad and Aykhan are playing a permutation puzzle game. Fuad challenges Aykhan to create a special sequence of numbers. To win the challenge, Aykhan must generate a “\textbf{composite sum permutation}”, a sequence where for every $i$ between $1$ and $n$ inclusive, the sum of the first $i$ numbers of the permutation $p$ of size $n$ is always composite. A positive integer $x$ is considered \textbf{composite} if it has more than two positive integer divisors. For instance, integers like $10, 25$, and $222$ are composite, while $1, 3, 31, 89, 97$, and $13$ are not. A sequence of positive integers $p = p_1, p_2, ..., p_n$ is defined as a \textbf{permutation} of length $n$ if it contains every integer between $1$ and $n$ inclusive exactly once. We’ll call a permutation $p = p_1, p_2, ..., p_n$ a “\textbf{composite sum permutation}” if, for every index $i$ between $1$ and $n$ inclusive, the sum of the first $i$ elements of $p$, denoted as $p_1 + p_2 + ... + p_i$, is a composite number. Help Aykhan to generate the required permutation by writing a program. \InputFile One single integer $n~(1 \le n \le 100)$. \OutputFile If no composite sum permutation of length $n$ exists, print a single integer $-1$. Otherwise, print $n$ integers $p_1, p_2, ..., p_n$ such that $p = p_1, p_2, ..., p_n$ is a “\textbf{composite sum permutation}”. If there are multiple composite sum permutations of length $n$, you may print any of them. \Examples In the first example for $n = 3$, there is no answer. In the second example for $n = 4$, we can generate permutation “$4~2~3~1$”. Compute the prefix sums: “$4, 6, 9, 10$”. Each of these sums is composite: $4 = 2 \cdot 2, 6 = 2 \cdot 3, 9 = 3 \cdot 3, 10 = 2 \cdot 5$". \Scoring This task consists of the following subtasks. If all tests of a subtask are passed, you will earn points for that subtask. \begin{enumerate} \item ($25$ points): $n \le 10$; \item ($75$ points): $no~additional~constrains$; \end{enumerate}
Time limit 1 second
Memory limit 128 MiB
Input example #1
3
Output example #1
-1
Input example #2
4
Output example #2
4 2 3 1
Source 2024, IDDA Cup, March 31, Problem D