Page **1** of **6**

Posted: **Wed Mar 06, 2002 3:28 am**

by **C8H10N4O2**

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**

by **Stefan Pochmann**

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**

by **Stefan Pochmann**

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**

by **C8H10N4O2**

Microsoft Visual C++ babies too much. It automatically fixes memory errors and stuff:o)

Posted: **Wed Mar 06, 2002 1:32 pm**

by **C8H10N4O2**

Wierd, the is definitely there on my computer...

Posted: **Sat Mar 16, 2002 2:42 pm**

by **junjieliang**

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**

by **Stefan Pochmann**

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**

by **junjieliang**

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**

by **arnsfelt**

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**

by **Stefan Pochmann**

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**

by **junjieliang**

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**

by **Revenger**

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

Readln(t);

for tt:=1 to t do begin

Readln(l);

for i:=1 to l do

if i<>l then

Read(Train

*)*

else

Readln(Train*);*

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**

by **Revenger**

I can't understand why I get WA

**Please, help me!**
[pascal]Program p299;

Const MaxL = 100;

Var L,Ans : Integer;

Train : Array[1..MaxL]of Integer;

i,j,k : Integer;

t,tt : Integer;

begin

Readln(t);

for tt:=1 to t do begin

Readln(l);

for i:=1 to l do

if i<>l then

Read(Train

*)*

else

Readln(Train*);*

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**

by **Rene**

Why my code is WA?

Please help me!

[cpp]#include <iostream.h>

struct node

{

int num;

node *next;

};

node *head,*last;

int dele ()

{

node *p;

p = head;

head = head -> next;

delete p;

return 0;

}

int swap ()

{

last -> next = head;

last = head;

head = head -> next;

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;

while (head -> next)

{

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**

by **Hisoka**