No wells P44291


Statement
 

pdf   zip

html

A sequence of numbers has a well if it contains three consecutive numbers such that the endpoints add up more than twice the one in the middle. Formally, (x1, x2, …, xn) has a well if it exists at least an i with 2 ≤ i ≤ n − 1 such that xi−1 + xi+1 > 2 xi.

Write a program that, given an integer n, prints all the sequences with no wells that can be obtained by reordering the sequence (1, 2, …, n).

Input

Input consists of several cases, each one with an n between 1 and 105.

Output

For every n, print all the permutations with no wells in lexicographical order. Print a line with 10 dashes at the end of every case.

Public test cases

  • Input

    2
4
7
1

    Output

    (1,2)
(2,1)
----------
(1,2,3,4)
(1,3,4,2)
(1,4,3,2)
(2,3,4,1)
(2,4,3,1)
(4,3,2,1)
----------
(1,2,3,4,5,6,7)
(1,3,4,5,6,7,2)
(1,3,5,7,6,4,2)
(1,7,6,5,4,3,2)
(2,3,4,5,6,7,1)
(2,4,6,7,5,3,1)
(2,7,6,5,4,3,1)
(7,6,5,4,3,2,1)
----------
(1)
----------
    • Information
    Author
    Albert Oliveras
    Language
    English
    Official solutions
    C++
    User solutions
    C++