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 :wink:

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? :wink:

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.:smile: 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 :cry: 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 :cry:
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
input

Code: Select all

1
5
1 3 4 2 5
output

Code: Select all

2