OJ Board

2 is the right answer?
why?
i think 3 is the right answer. And my code get the answer 3.

I know your program will produce 3 for this input. and the right output is 2.
this is that proses:

1 3 4 2 5

proses 1 : 1 3 2 4 5
proses 2 : 1 2 3 4 5

end of proses.

GOOD LUCK.......

oh,i see.
and i have changed a new way to slove this problem and got accepted.
Thanx.

I don't understand why my program is wrong
please give any comments....


[pascal]
program p229 (input,output);
type
aset=array[1..50] of integer;
var
a:aset;
n,nn,train,j,k:integer;

function bsort(var a:aset) :integer;
var
j,k,temp,n:integer;
begin
n:=0;
for j:=nn downto 2 do
for k:=1 to nn-1 do
if a[k] > a[k+1] then begin
n:=n+1;
temp:=a[k];
a[k]:=a[k+1];
a[k+1]:=temp;
end;
bsort:=n;
end;

begin
while not eof(input) do begin
readln(n);
if eof(input) then exit;
for j:=1 to n do begin
readln(nn);
if eof(input) then exit;
for k:=1 to nn do begin
read(train);
if eof(input) then exit;
a[k]:=train;
end;
readln;
writeln('Optimal train swapping takes ',bsort(a),' swaps.');
end;
end;
end.
[/pascal]

i think there is no need to check eof after reading each number.

in fact, i got AC with your program after all statements related to eof(input) are removed.

thanks for your comments.

Why 299 WA? I can't figure it out!!!
[c]/* 299 */
#include<stdio.h>
#define MAX 95
void main(void)
{
unsigned int maxnum,i,j,pass,maxtimes,times,n[MAX],temp;

scanf("%u",&maxtimes);
for(;maxtimes;maxtimes--){
scanf("%d",&maxnum);
for(i=0;i<maxnum;i++)scanf("%u",&n);
times=0,pass=1;
for(j=maxnum-1;j&&pass;j--)
for(pass=0,i=0;i<j;i++)
if(n>n[i+1]){
times++,pass=1;
temp=n[i+1];n[i+1]=n;n=temp;
}
printf("Optimal train swapping takes %u swaps.\n",times);
}
}[/c]

unsigned int maxnum,i,j,pass,maxtimes,times,n[MAX],temp;

scanf("%d",&maxtimes);

you have declared maxtimes to be of type unsigned int, but your are using '%d'.

I've changed %d to %u, but the result cganged to "Time Limit Exceeded". I use "Bubble Sort" and save how much times it count!
I know bubble sort isn't a powerful sort, but a friend of mine use this way to solve it in the past, and he solved then. But when I transfered his codes yesterday, the result is "Time Limit Exceeded"
Does someone know how to figure the times but use less time? Could you help me?Thank you!!!

BubbleSort is efficient enough for this question.

Of course, if you really want to optimize your code, you may use MergeSort

Well, I think first you should locate the train with number n. Hopefully by locating the trains, the time will be reduced. Example:
5 trains:
3 4 1 5 2
We expect the train will be 1 2 3 4 5.
1. We want to arrange the train 1 (currently in pos 3) become:
3 4 1 5 2 -> 3 1 4 5 2 -> 1 3 4 5 2
2. Now train no 2 (currently in the last position):
1 3 4 5 2 -> 1 3 4 2 5 -> 1 3 2 4 5 -> 1 2 3 4 5
Well, since the trains are already in order, we don't have to proceed.
Hope it helps !!
[/c]

Well, I just changed "unsigned int" to "int" ,
"scanf("%u",&maxtimes);"
into
"while(scanf("%d",&maxtimes)==1)"

Then, it accepted!

I thought it should be an easy one, but i don't know why i didn't get through.....
i used the bubble sort and count the steps of sorting, is this algorithm all right for problem 299?? Thanks in advance! here is my code: (in Java)

[java]
import java.util.*;

class Main{
public static void main(String [] args){
String in;
int c, i, size, j, k, t, n;
c = Integer.parseInt(Main.readLine());
StringTokenizer st;
int[] a;
for (i=0 ; i<c ; i++){
if (i!=0)System.out.println();
n=0;
size = Integer.parseInt(Main.readLine());
a = new int [size];
in = Main.readLine();
st = new StringTokenizer(in);
for (j=0 ; j<size; j++){
a[j] = Integer.parseInt(st.nextToken());
}
for (j=0 ; j<size-1 ; j++){
for (k=0 ; k<size-1-j ; k++){
if (a[k]>a[k+1]){
t = a[k];
a[k] = a[k+1];
a[k+1] = t;
n++;
}
}
}
System.out.print("Optical train swapping takes " + n + " swaps.");
}
}

static String readLine(){return token( "\n\r" );}


/* read token from stdIn with standard delims */
static String token( ){return token( " \n\r\t" );}


/* read token from stdIn with custom delims */
/* returns null for end of file or any exceptions */
static String token( String delim ){
char c = delim.charAt(0);
StringBuffer s = new StringBuffer("");
try{
while( delim.indexOf( (int) c ) != -1 && c != 65535 )
c = (char) System.in.read();
while( delim.indexOf( (int) c ) == -1 && c != 65535 ){
s.append( (char) c );
c = (char) System.in.read();
}
}catch( Exception e ){ return (null); }
if( s.toString().equals("") ) return null;
return s.toString();
}

}[/java]

Your algorithm is good for this problems, I got AC using the same approach. Check your code for reading the input one more time, try to replace the core of your code with something like:[cpp] while(flag){
flag = false;
for(long i = 0; i < n - 1; i++)
if(data > data[i + 1]){
swap(data, data[i + 1]);
ans++;
flag = true;
}
}[/cpp]yes, it's is slower in some cases, but it's accepted It's better to write more robust then faster code before you get AC.
Hope this will help.

Did you allready correct the following mistake:

[java]System.out.print("Optical train swapping takes " + n + " swaps."); [/java]

It's not the "Optical train swapping " that you are looking for - but the
"Optimal"...

Robert