1996 Canadian Computing Competition, Stage 2

Day 1, Problem 1: Train Swapping

At an old railway station, you may still encounter one of the last remaining "train swappers". A train swapper is an employee of the railroad, whose sole job it is to rearrange the carriages of trains.

Once the carriages are arranged in the optimal order, all the train driver has to do is drop the carriages off, one by one, at the stations for which the load is meant.

The title "train swapper" stems from the first person who performed this task, at a station close to a railway bridge. Instead of opening up vertically, the bridge rotated around a piller in the center of the river. After rotating the bridge 90 degrees, boats could pass left or right. The first train swapper had discovered that the bridge could be operated with at most two carriages on it. By rotating the bridge 180 degrees, the carriages switched place, allowing him to rearrange the carriages (as a side effect, the carriages then faced the opposite directions, but train carriages can move either way, so who cares).

Now that almost all train swappers have died out, the railway company would like to automate their operation. Part of the program to be developed is a routine which decides, for a given train, the least number of swaps of two adjacent carriages necessary to order the train. Your assignment is to create a routine that computes the minimal number of swaps.

Input specification

The input contains on the first line the number of test cases (N). Each test case consists of two input lines. The first line of a test case contains an integer L, determining the length of the train (0 ≤ L ≤ 50). The second line of a test case contains a permutation of the numbers 1 through L, indicating the current order of the carriages. The carriages should be ordered such that carriage 1 comes first, then 2, etc., with carriage L coming last.

Output specification

For each test case output the sentence: "Optimal train swapping takes S swap(s)." where S is an integer representing the minimal number of swaps to order the train.

Sample input

3
3
1 3 2
4
4 3 2 1
2
2 1

Sample output

Optimal train swapping takes 1 swap(s).
Optimal train swapping takes 6 swap(s).
Optimal train swapping takes 1 swap(s).

All Submissions
Best Solutions

Point Value: 7
Time Limit: 2.00s
Memory Limit: 16M
Added: Jun 24, 2013

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Hello,
My solution appears to work on the test data from CEMC (once I figured out how to handle the 0 case, its a bit unclear), but it still crashes on the autograder.  Can anyone point out my error?

Apologies for this. The test data we used included carriage returns. I've stripped them out and rejudged your latest submission, which now gets AC.

To avoid this in the future, consider using input().strip().

Thanks, jargon.

Just to be clear, we do have an unofficial policy that test data should not contain carriage returns. So it is our fault if it does, not that of users. However, one should be aware that actual contests might screw this up, so jargon's advice is on point.

Yeah, I thought that we did but I couldn't find it on the readme...

Haha period at the end :/

at least you don't have to worry about the grammar in swap(s)