Two rows of numbers P83712


Statement
 

pdf   zip

thehtml

You have 2n different numbers. Write a program to find all the ways to put the numbers in two rows x1xn and y1yn so that:

  • x1 < x2 < … < xn−1 < xn ,
  • y1 < y2 < … < yn−1 < yn ,
  • for every i, it holds xi < yi.

Input

Input consists of n, followed by 2n different integer numbers. Assume 1 ≤ n ≤ 11.

Output

Print all the ways to put the numbers fulfilling the required conditions. For every way, print three lines: two rows with xi and yi separated by spaces, and an empty line. Print the solutions in lexicographical order: first, those with the smaller x1, in case of a tie, those with the smaller x2, …, in case of a tie, those with the smaller xn, in case of a tie, those with the smaller y1, …

Public test cases
  • Input

    3
    1 2 3 4 5 6
    

    Output

    1 2 3
    4 5 6
    
    1 2 4
    3 5 6
    
    1 2 5
    3 4 6
    
    1 3 4
    2 5 6
    
    1 3 5
    2 4 6
    
    
  • Input

    1
    0 -200
    

    Output

    -200
    0
    
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++ Python