Description
You and your crew just successfully landed on Mars, and due to an unforeseen storm you have
evacuated your base and returned to orbit. As your pod was about to dock with your
interplanetary transportation vehicle one of your crew members, Fred, sneezed and ripped out a
section of cables from the wall. This cause your pod to spin out of control and descend towards
Mar’s surface.
Fred sprang into action and begun plugging in the cables. However, Fred did not connect the
correct cables and the pod crashed into the surface…
The simulation terminates and you confront Fred. “It wasn’t me,” he exclaims. You sigh, and
begin writing a program that can help prevent such a disaster from occurring again.
Problem
You are given a list of cables (and their lengths) that were plugged into a wall. The way in which
these cables were plugged in was linear. That is there are exactly n cable and 2n evenly spaced
holes, where each hole is in a single row. Each cable has some integer length which will denote
the number of holes the cable can cross over. You know that each cable was taught before they
were removed. If a cable can cross two holes, then it will have crossed exactly two holes in the
correct configuration. Additionally each hole has exactly one cable end plugged into it.
You need to return to the user the number of different valid configurations, where two
configurations are different, if at least one hole is connected to a different one via the cable
plugged into it. Additionally, print out at least one valid configuration if one exists.
Input Specification
The first line of input is a single positive integer, n (n ≤ 9), representing the number of cables.
The following line will contain n integers representing the number of holes a cable can (and
should) bypass. The number of bypassed holes will be no more than 2n.
Output Specification
The first line of output should contain a single non-negative integer, a, representing the number
of unique, valid wire configurations. If the value of a is positive, then the output will have a
second line. The second line should contain 2n space-separated integers, where the i-th integer
represents the cable length used in the i-th hole.
Input Output Example
Input Output
4
0 1 2 3
6
3 0 0 2 3 1 2 1
3
0 3 3
1
3 3 0 0 3 3
6
0 1 2 3 4 5
0
Explanation
Case 1
There are 6 unique configurations
0 0 2 3 1 2 1 3
0 0 3 1 2 1 3 2
1 2 1 3 2 0 0 3
2 3 1 2 1 3 0 0
3 0 0 2 3 1 2 1
3 1 2 1 3 2 0 0
Case 2
There is only one unique solution. Note that having the arrangement
31 32 0 0 31 32
is equivalent to having
32 31 0 0 32 31
Thus there is exactly one solution.
Case 3
There is no valid solutions that keeps every cable with a longest possible length, so the answer is
0. There is no second line of output, because there is no valid arrangement.
Grading Information
Read/write in from standard input/output – 5 points
Comments, variable names, whitespace usage – 15 points
Permute the cables using recursion – 10 points
Use a permutation to place cables meaningfully – 10 points
Check the validity of an arrangement – 10 points
Your program will be tested on 10 test cases – 5 points each
No points will be awarded to programs that do not compile.
Solutions without recursion will receive a maximum of 50 points