Page 1 of 6
Posted: Wed Mar 06, 2002 3:28 am
This should a simple problem, no? I keep getting WA. I don't know what is wrong. Please help!

Code: Select all

``````#include <stdio.h>

void main()
{
int i,j,k,m,n,t,A[100],Swaps;

scanf("%d",&m);
for(k=0;k<m;k++)
{
Swaps=0;
scanf("%d",&n);

for(j=0;j<n;j++)
{
scanf("%d",&A[j]);
}

for(i=0;i<n-1;i++)
{
for(j=n-1;j>i;j--)
{
if(A[j]<A[j-1])
{
t=A[j];
A[j]=A[j-1];
A[j-1]=t;
Swaps++;
}
}
}

printf("Optimal train swapping takes %d swaps.n",Swaps);
}
}
``````

Posted: Wed Mar 06, 2002 5:22 am
Maybe you should sometimes run your programs on your own computer before submitting them. The you would've probably noticed that you output an 'n' instead of a 'n'.

Posted: Wed Mar 06, 2002 6:52 am
Btw, I just realized that one does not actually has to sort the sequence. Simply determining the "degree of unsortedness" is enough. I'll leave it to you to find out what I mean with that

Posted: Wed Mar 06, 2002 1:29 pm
Microsoft Visual C++ babies too much. It automatically fixes memory errors and stuff:o)

Posted: Wed Mar 06, 2002 1:32 pm
Wierd, the is definitely there on my computer...

Posted: Sat Mar 16, 2002 2:42 pm
I presume your "degree of unsortness" refers to the number of inversions. Is there a way to do this in linear time?

Posted: Sun Mar 17, 2002 7:20 am
Please define "inversions". But I guess you mean the right thing. Linear time possible? Hmm, maybe. I'll have to think about it. Intuitively, I would say yes.

Posted: Sun Mar 17, 2002 5:00 pm
I think I mean it like A > A[j] and i < j. Not very good with this kind of mathematical notations. But actually I don't really need a linear time, just anything that's better than quadratic...

Posted: Sun Mar 17, 2002 11:58 pm
There is a very nice O(n log n) solution, easily derived from mergesort.

Consider returning both the sorted list and the number of inversions and look into how to modify the merge.

Posted: Mon Mar 18, 2002 4:19 am
junjieliang: So you "need" something that's better than quadratic? Unfortunately, the input cases are so small, that quadratic solutions go through in zero time. What do you need it for? A homework assignment?

I tried to get it down to linear time today, but didn't succeed. Nothing really worked. But I'm not yet ready to give it up.

Posted: Mon Mar 18, 2002 8:45 am
Fine, I do have a motive. It's for solving another problem, where quadratic would be too slow (but that's over at timus). Since this was brought up I decided to ask around...

Posted: Sat Jun 15, 2002 10:13 am
This problem is easy, but I get WA Can anybody find an error in this program? Please!

[pascal]Program p299;

Const MaxL = 100;

Var L,Ans : Integer;
Train : Array[1..MaxL]of Integer;
i,j,k : Integer;
t,tt : Integer;

begin
for tt:=1 to t do begin
for i:=1 to l do
if i<>l then
else
ans:=0;
for i:=1 to l-1 do
for j:=l downto i+1 do
if Train[j]<Train[j-1] then begin
k:=Train[j];
Train[j]:=Train[j-1];
Train[j-1]:=k;
ans:=ans+1;
end;
Write('Optimal train swapping takes ');
Writeln(ans:0,' swaps.');
end;
end.[/pascal]

### 299 - Train Swapping

Posted: Mon Jun 24, 2002 11:41 pm
I can't understand why I get WA

[pascal]Program p299;

Const MaxL = 100;

Var L,Ans : Integer;
Train : Array[1..MaxL]of Integer;
i,j,k : Integer;
t,tt : Integer;

begin
for tt:=1 to t do begin
for i:=1 to l do
if i<>l then
else
ans:=0;
for i:=1 to l-1 do
for j:=l downto i+1 do
if Train[j]<Train[j-1] then begin
k:=Train[j];
Train[j]:=Train[j-1];
Train[j-1]:=k;
ans:=ans+1;
end;
Write('Optimal train swapping takes ');
Writeln(ans:0,' swaps.');
end;
end.[/pascal]

### 299 WA

Posted: Sat May 10, 2003 1:27 pm
Why my code is WA?

[cpp]#include <iostream.h>

struct node
{
int num;
node *next;
};

int dele ()
{
node *p;
delete p;
return 0;
}

int swap ()
{
last -> next = NULL;
return 0;
}

int main()
{
int test,lenth,swaps,i,j;
node *p;
cin >> test;
for (i = 1;i <= test;i++)
{
swaps = 0;
cin >> lenth;
for (j = 1;j <= lenth;j++)
{
last = new node;
if (j == 1) head = last;
else p -> next = last;
cin >> last -> num;
last -> next = NULL;
p = last;
}
j = 1;
{
if (head -> num == j)
{
dele ();
j++;
}
else
{
swap ();
swaps++;
}
}
cout << "Optimal train swapping takes " << swaps << " swaps." << endl;
}
return 0;
}[/cpp]

Posted: Sun May 11, 2003 7:54 am
input

Code: Select all

``````1
5
1 3 4 2 5``````
output

Code: Select all

``2``