299 - Train Swapping
Moderator: Board moderators
299 - can anyone help me
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]
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]
thanks cytse, it works !!!!
thanks for your comments.
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]
[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.
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!!!
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
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
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
-
- 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]
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]
It's been Accepted!!
Well, I just changed "unsigned int" to "int" ,
"scanf("%u",&maxtimes);"
into
"while(scanf("%d",&maxtimes)==1)"
Then, it accepted!
"scanf("%u",&maxtimes);"
into
"while(scanf("%d",&maxtimes)==1)"
Then, it accepted!

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

Hope this will help.
