Page 4 of 6

10327

Posted: Mon Aug 21, 2006 3:58 pm
by Gungchil
Plz help me to find the mistake
Here is my code
#include<stdio.h>
int main()
{
long int n,i,j,temp,a[100000],k,count=0,p;
while(scanf("%ld",&n)==1)
{
for(i=0;i<n;i++)
scanf("%ld",&a);
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
{
if(a>a[j])
{
temp=a;
a=a[j];
a[j]=temp;
count++;
}
}
printf("Minimum exchange operations : %ld\n",count);
count=0;
}
return 0;
}

10327

Posted: Thu Nov 02, 2006 5:46 pm
by Rushow
This is my source code. Anyone can tell what's the problem in it?



/* p10327 */
/* Flip Sort */

#include<stdio.h>
void main()
{
long s[1002],n,i,j,x,m;
while(scanf("%ld",&n)!=EOF)
{
m=0;
for(i=0;i<n;i++)
scanf("%d",&s);
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
if(s>s[j])
{
x=s;
s=s[j];
s[j]=x;
m++;
}
}

}

printf("Minimum exchange operations : %ld\n",m);
}
}

Posted: Thu Nov 16, 2006 12:34 pm
by Tariq Shahriar
Rushow, you forgot the terms & conditions of the problem
only one operation ( Flip ) is available and that is you can exchange two adjacent terms
but your algorithm didn't perform like this.
think about second sample input-
2 3 1
in your algo, first interchange occurs between 2 and 1, but 2 and 1 is not adjacent. always swap between two adjacent (consecutive positioned) number (when needed).
so your algo is not flip (bubble) sort, actually replacement sort.

recently, our teacher taught us bubble sort, but you mistook. so bad.
let observe step by step, how flip sort will work
(currently comparing numbers will be shown in red)-
3 2 1 //the initial position of the array n=3 elements
3 2 1 //swap. after swapping: 2 3 1
2 3 1 //swap
2 1 3 //after n-1 comparison the largest element will in last position. so no eed to compare with it latter. again start from the beginning)
2 1 3 //swap
1 2 3 //after n-2 comparison the 2nd largest element will in 2nd last position. so no need to compare with it latter. there has only one element. so sorting was completed)
we swapped for 3 times. so ans=3.

to clear more, u can also get help from: http://www.comp.nus.edu.sg/~stevenha/pr ... rting.html

// N.B. while writing code, use BBcode tags. visit BBcode Guide

Posted: Sun Jul 22, 2007 12:35 pm
by newton
thank you jainal.
you are really a genish!!!

Posted: Sun Jul 22, 2007 2:40 pm
by jainal cse du
Hi Newton,you have to count only minimum exchange operations.
So,replace it .

Code: Select all

for(i = 0;i < num-1; i++) 
{ 
         for(j = i+1;j < num;j++) 
         { 
               if(array[i] > array[j]) 
              { 
                    cnt++; 
                    tmp = array[i]; 
                    array[i] = array[j]; 
                    array[j] = tmp; 
              } 
         } 
} 

By following

Code: Select all

cnt = 0;
for(i = 0;i < num; i++) 
{ 
         for(j = i+1;j < num;j++) 
         { 
              if(array[i] > array[j]) 
                     cnt++;  
         } 
} 


Posted: Mon Aug 20, 2007 11:37 am
by andysoft
HOW can this code give WA?
I got already 7 (or like that) WAs on this easy prob.

Code: Select all

program Project1;

{$APPTYPE CONSOLE}

uses
  SysUtils;

var
  a: array [1..1000] of integer;
  i,j,k,l,n: integer;
  fl: boolean;

begin
  while not eof do
  begin
    readln (n);
    if eof then break;
    for i:=1 to n do
      read (a[i]);
    k := 0;
    fl := true;
    while fl do
    begin
      fl := false;
      for j:=1 to n-1 do
        if a[j]>a[j+1] then
        begin
          inc(k);
          fl := true;
          l := a[j];
          a[j] := a[j+1];
          a[j+1] := l;
          fl := true
        end
    end;
    writeln ('Minimum exchange operations : ',k)
  end;
end.


Posted: Mon Aug 20, 2007 11:54 am
by mf
Maybe your program actually gets a runtime error.
Judge doesn't detect runtime errors for Pascal programs, and incorrectly gives WA verdict instead.

10327....

Posted: Wed Jan 30, 2008 9:04 am
by Obaida
I don't know why judge give me worng answer.... plezz help me.... This is too..... much crazy.

Code: Select all

removed

Posted: Tue Feb 12, 2008 8:10 pm
by sapnil
Cheque it

Code: Select all

Input:
5
5 1 3 5 1
output:
Minimum exchange operations : 5
Thanks
Keep posting
sapnil

Thanks....

Posted: Tue Feb 19, 2008 11:25 am
by Obaida
8) Thank You..... Got Ac.... 8)

10327 - Flip Sort --> more inputs

Posted: Thu Aug 28, 2008 6:16 pm
by carliros
Input
5
6 2 1 5 4
8
3 5 8 2 1 9 7 0
2
0 0
12
0 1 2 5 4 1 2 0 5 0 7 9
30
21 5 6 5 8 452 12 5 96 21 21 5 6 5 8 452 12 5 96 21 21 5 6 5 8 452 12 5 96 21 21 5 6 5 8 452 12 5 96 21 21 5 6 5 8 452 12 5 96 21

output
Minimum exchange operations : 6
Minimum exchange operations : 16
Minimum exchange operations : 0
Minimum exchange operations : 19
Minimum exchange operations : 168
Minimum exchange operations : 67

Re: 10327 - Flip Sort --> more inputs

Posted: Sun Sep 14, 2008 1:17 pm
by debugger
carliros wrote: Input
Minimum exchange operations : 6
Minimum exchange operations : 16
Minimum exchange operations : 0
Minimum exchange operations : 19
Minimum exchange operations : 168
Minimum exchange operations : 67
Do your code is accepted?? I am quite confused! :roll: Though i do not get ac, but your output have increased my confusion. :roll: :oops:

Re: 10327 - Flip Sort

Posted: Sun Sep 21, 2008 3:12 pm
by carliros
yes, my code was AC.

Re: 10327 - Flip Sort

Posted: Mon Nov 10, 2008 12:09 am
by pok
this is my code. i got WA..
but what is wrong in this code?

#include<stdio.h>

int main()
{
long int n,a[1001];

while(scanf("%ld",&n)==1)
{
long int i,j,x=0,temp;

for(i=0;i<n;i++)
scanf("%ld",&a);

for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
if(a>a[j])
{
temp=a;
a=a[j];
a[j]=temp;
x++;
}

printf("Minimum exchange operations : %ld\n",x);
}

return 0;

}

pls help me..

Re: 10327 - Flip Sort

Posted: Mon Nov 10, 2008 10:41 am
by Obaida
You didn't need to do exchange but count how many exchange are available.

Ok, check this input,

Code: Select all

Input:
5
5 1 3 5 1
output:
Minimum exchange operations : 5
Hope you find your mistake. :wink: