OJ Board

This should a simple problem, no? I keep getting WA. I don't know what is wrong. Please help!

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'.

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

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

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

I presume your "degree of unsortness" refers to the number of inversions. Is there a way to do this in linear time?

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.

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

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.

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.

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

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]

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]

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]

input output