ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Разделы > Арифметика > задача:


50267 - Interesting permutations

Гость
• Обсуждение задачи (1)

Задачи раздела

• 50243 - Sum of digits
• 50241 - Greatest common divisor
• 50240 - The numbers that are divisi...
• 50242 - Numbers whose sum of the...
• 50248 - Power of two
• 50641 - Strong Prime Power
• 50249 - Ladders
• 50247 - Missing numbers
• 50267 - Interesting permutations
• 50640 - Cubes
• 50377 - kth Permutation
• 50341 - Separate Into Digits
• 50424 - Area
• 50335 - Five Math Operators
• 50299 - Median
• 50301 - Fractions to Decimals
• 50304 - Number Pattern

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Автор: Павел Кузнецов, ПГУ.

A permutation is a sequence of N different numbers from 1 to N. For example, there are six permutations for N = 3:
  • 1, 2, 3
  • 1, 3, 2
  • 2, 1, 3
  • 2, 3, 1
  • 3, 1, 2
  • 3, 2, 1
We say that a permutation is interesting if it does not contain 3 numbers that make an arithmetic progression. E.g., all the permutations for N = 3 above are interesting, except the first and the last. On the contrary, permutation 5, 1, 2, 4, 3 is not interesting, since it contains numbers 1, 2, 3 that make an arithmetic progression. It does not matter that there is number 4 between 2 and 3. The ascending or descending order of numbers is all that matters. Also you can take 5, 4, 3, since these numbers also make the arithmetic progression.

Your task is to find at least one interesting permutation for number N, if there exists any.

Input
The first line contains a single integer N (3 ≤ N ≤ 100000).
Output
The first line of output should contain the word "NO" (capital letters and no quotes) if there are no interesting permutations for N. Otherwise, the first line of output should contain "YES" (capital letters and no quotes), and the second line should contain the permutation itself. Numbers in permutation should be separated by spaces. If there are several solutions, you may output any of them.

Input 1 Output 1
3
YES
3 1 2
Input 2 Output 2
5
YES
4 2 3 1 5

Для отправки решений необходимо выполнить вход.

www.contester.ru