## 299 - Train Swapping

Moderator: Board moderators

Rene
New poster
Posts: 13
Joined: Mon May 05, 2003 4:40 am
Location: Shanghai,China
why?
i think 3 is the right answer. And my code get the answer 3.

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia
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.......

Rene
New poster
Posts: 13
Joined: Mon May 05, 2003 4:40 am
Location: Shanghai,China
oh,i see.
and i have changed a new way to slove this problem and got accepted.
Thanx.

kenny1har
New poster
Posts: 7
Joined: Fri May 09, 2003 2:30 am

### 299 - can anyone help me

I don't understand why my program is wrong

[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
if eof(input) then exit;
for j:=1 to n do begin
if eof(input) then exit;
for k:=1 to nn do begin
if eof(input) then exit;
a[k]:=train;
end;
writeln('Optimal train swapping takes ',bsort(a),' swaps.');
end;
end;
end.
[/pascal]

cytse
Learning poster
Posts: 67
Joined: Mon Sep 16, 2002 2:47 pm
Location: Hong Kong
Contact:
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.

kenny1har
New poster
Posts: 7
Joined: Fri May 09, 2003 2:30 am

### thanks cytse, it works !!!!

jai166
New poster
Posts: 10
Joined: Mon May 12, 2003 11:10 am

### Why 299 WA?

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]
Last edited by jai166 on Tue Jul 29, 2003 9:36 am, edited 2 times in total.

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

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

jai166
New poster
Posts: 10
Joined: Mon May 12, 2003 11:10 am

### Sorry, Time Limit Exceeded...

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

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
BubbleSort is efficient enough for this question.

Of course, if you really want to optimize your code, you may use MergeSort
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Joseph Kurniawan
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia
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]

jai166
New poster
Posts: 10
Joined: Mon May 12, 2003 11:10 am

### It's been Accepted!!

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

Then, it accepted!

boyeric
New poster
Posts: 6
Joined: Sun Jun 20, 2004 5:08 pm

### WA 299..... somebody help???

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;
StringTokenizer st;
int[] a;
for (i=0 ; i<c ; i++){
if (i!=0)System.out.println();
n=0;
a = new int [size];
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.");
}
}

/* read token from stdIn with standard delims */

/* 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 )
while( delim.indexOf( (int) c ) == -1 && c != 65535 ){
s.append( (char) c );
}
}catch( Exception e ){ return (null); }
if( s.toString().equals("") ) return null;
return s.toString();
}

}[/java]

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver
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.

Robert
New poster
Posts: 2
Joined: Sun Jul 04, 2004 2:39 pm
Location: Germany
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