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 pillar 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 direction, 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 that routine.

Input

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

For each test case output the sentence: ‘Optimal train swapping takes S swaps.’ where S is an

integer.

Sample Input

3

3

1 3 2

4

4 3 2 1

2

2 1

Sample Output

Optimal train swapping takes 1 swaps.

Optimal train swapping takes 6 swaps.

Optimal train swapping takes 1 swaps.

## Solve Code

```
#include<stdio.h>
int main()
{ int t,n,i,j,tmp;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
int arr[n],m=0;
for(i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
for ( i = 0; i <n-1; i++)
{
for (j = 0; j < n-i-1; j++)
{
if (arr[j] > arr[j+1])
{
m++;
tmp = arr[j];
arr[j]=arr[j+1];
arr[j+1]=tmp;
}
}
}
printf("Optimal train swapping takes %d swaps.\n",m);
}
return 0;
}
```

- Scarecrow UVA – 12405 | Solution
- Hackerland Radio Transmitters- HackerRank | Solution
- Age Sort UVA – 11462 | Solution
- Helpful Maths CodeForces – 339A | Solve
- Train Swapping UVA – 299 |Solution

Thank you, I’ve recently been looking for information approximately this subject for ages and yours is the greatest I’ve discovered till now.

But, what in regards to the bottom line? Are you positive concerning the source?

My family all the time say that I am killing my

time here at net, but I know I am getting experience daily by reading such good content.

adreamoftrains web hosting

I visited multiple blogs except the audio quality for audio songs existing at this website is truly wonderful.

It’s really a cool and helpful piece of information. I am happy that you just shared this

helpful information with us. Please keep us informed like this.

Thank you for sharing.

Hi there! Do you use Twitter? I’d like to follow you if that would

be ok. I’m undoubtedly enjoying your blog and look

forward to new posts.

I’m not sure exactly why but this blog is loading extremely slow for me.

Is anyone else having this issue or is it a issue on my end?

I’ll check back later on and see if the problem still exists.

Remarkable issues here. I am very satisfied to see

your post. Thanks a lot and I’m looking ahead to touch you.

Will you please drop me a e-mail?

Undeniably believe that which you stated. Your favorite reason seemed to

be on the net the easiest thing to be aware of. I say to you, I certainly get irked

while people think about worries that they plainly do not know about.

You managed to hit the nail upon the top and defined out the whole thing without having side-effects , people could take a signal.

Will likely be back to get more. Thanks