WM06 - Soccer Choreography

Mr. Bitmann, the coach of the national soccer team of Bitland, is a perfectionist. He taught his players optimal tactics and improved their endurance and shape. So they qualified for the soccer woldcup this year. Due to his perfectionism the coach attaches importance not only to the performance in the game but also before the game. So he told the team captain in what formation the team should assemble before the national anthem is played. Since each of the 11 team members has a unique number between 1 and 11 on his shirt, he can represent the formation as a permutation of numbers.

Before the first game the coach told the captain that the team should line up in increasing order (picture (d)). But some players forgot the ordering and the orientation of the formation like in picture (a). Only player 1 has the right orientation. The coach went nearly mad when he saw this desaster! How could he solve the problem?

scenario example

"Hmmm... I'll let my players dance!". A great idea! He took his notebook and started to create a choreography which leads to his expected formation. Due to the fact that no one of the players took dancing lessons he restricts his dance to one basic move: One player or more players who stand side by side can turn 180 degrees around the center of the move. Picture (b) contains an example: The players

-11 -10 -9 -2

(we mark players which stand in the wrong direction with a minus) can do one move to

2 9 10 11

As perfect as he is he calculated a dance with a minimum number of moves. It works perfectly and now he's planning to do dancing performances with teams with more than 11 members. So he needs your help to find optimal dancing moves...

Input

Each testcase starts with the number of team members n (0<=n< 2200). The next lines represent the formation at the beginning and the expected formation at the end of the choreography.

Output

For each testcase output m, the minimal number of moves which are necessary to reach the expected formation. The next m+1 lines should represent one possible scenario of moves.

Example

Input:
11
-5 -4 -3 -8 -7 -6 1 -11 -10 -9 -2
1 2 3 4 5 6 7 8 9 10 11
11
1 2 3 -4 -5 -6 -7 -8 -9 10 11
11 9 8 7 6 5 4 3 2 10 1
0

Output:
3 Steps
-5 -4 -3 -8 -7 -6 +1 -11 -10 -9 -2
-5 -4 -3 -8 -7 -6 +1 +2 +9 +10 +11
-5 -4 -3 -2 -1 +6 +7 +8 +9 +10 +11
+1 +2 +3 +4 +5 +6 +7 +8 +9 +10 +11
5 Steps
+1 +2 +3 -4 -5 -6 -7 -8 -9 +10 +11
+1 +2 -3 -4 -5 -6 -7 -8 -9 +10 +11
+1 -2 -3 -4 -5 -6 -7 -8 -9 +10 +11
+1 -2 -3 -4 -5 -6 -7 -8 -9 -11 -10
+11 +9 +8 +7 +6 +5 +4 +3 +2 -1 -10
+11 +9 +8 +7 +6 +5 +4 +3 +2 +10 +1

Added by:Simon
Date:2006-05-11
Time limit:8s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST WHITESPACE

hide comments
2014-03-11 18:22:28 Mitch Schwartz
@ওয়াসী (Wasi): I wrote half of a solution over a year ago and set it aside because it was tiring, but it's on my list of things. Also, publishing a harder variant of this problem. :)
2014-03-11 17:55:05 ওয়াসী (Wasi)
This is the oldest question(almost 8 years old) with no user AC! I am really curious to see who gets the first AC :)
2014-02-10 21:12:06 Siddhartha Sinha
Comment Deleted.

Last edit: 2015-07-23 19:15:05
2012-08-28 18:50:32 (T_T)
why does it have language limitations?
2012-05-16 13:46:25 :D
Did a rejudge was done after time limit changes?
2012-02-04 19:13:41 Laplace
wait for me ,I will solve it within 6 years(before 2018)
2011-11-16 11:48:44 Adrian Kuegel
@jyothish soman: you are wrong, in this problem it is not required that the reversals always include the first element, so it is not the burnt pancake problem. The problem posed here can really be solved in O(n^2) time, and there are published papers which describe how.

Last edit: 2011-11-24 11:37:02
2011-11-16 11:45:04 Adrian Kuegel
The time limit was relaxed a bit. A reasonably fast O(n^2) solution should give accepted. The official solution takes at most 2.6 seconds on the largest input file.
@Johannes: as far as I can see your algorithm is exponential; you need an O(n^2) algorithm to get accepted.
@Nima Cao: your algorithm gives suboptimal answers. Most of the internal errors have been because you had freopen in your code. After the rejudge this has turned into WA.
2011-05-10 10:52:44 jyothish soman
This is actually a burnt pancake prefix reversal graph diameter problem, in short, cannot be solved in any practical time
2010-10-01 07:50:15 Nima Cao
The correct algorithm (O(n^2)) also can't accepted, because of the output is too ... huge, so the result would be "internal error" instead of "accepted". I have an algorithm with O(n^2) and fast enough.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.